题目链接:
普通版:
https://www.luogu.org/problemnew/show/P1028
数据加强版:
https://www.luogu.org/problemnew/show/P2240
中间插一段,奇怪了,我明明想到的是最好的那种递推方法,结果写着写着忘记了,写成最差的递推方法
所以中间插一段被我遗忘的好方法
这个也是这题的书上的答案
#include<bits/stdc++.h>
using namespace std;
int a[];
int main()
{
int n;
cin>>n;
a[]=;
for(int i=;i<=n;i++)
{
a[i]=a[i-];
if(i%==)
a[i]=a[i-]+a[i/];
}
cout<<a[i];
return ;
}
稍微解释一下:
举个例子就好了
a[5]=a[4]
a[6]=a[5]+a[6/3],那个a[6/3]就是a[3],因为相对于a[4]来说a[6]多了个a[3]的全部子数字
因为a[4]只能分解1~2
a[5]同a[4]一样
而a[6]可以分解1~3
所以a[6]多个a[3]
以下为自己写的垃圾方法:
基本思路:
@1:基本递推:
第n个数,它产生n/2个新的数,由于1~n/2都小于n,所以可以用递推,都计算到n了那么1~n/2的值肯定都已知了
@2:边缘条件:
我们把n=1和n=0时结果都为1都一开始就初始化好,作为初始条件
@3:细节
ps:这个地方好像有更好的办法而不是用奇葩的+1法,可是我懒得想了
在具体的数组中,a[n]应该是不包括n本身的所有子数字数目,为什么不能包括本身呢,因为后面要通过前面的数据递推
比如说a[6]=6/2 +a[1] + a[2] +a[3],那么其实是a[6]= 1+a[1] + 1+a[2] + 1+a[3],所以最后都要加回来
@4:规律
这个结果有奇偶的规律,比如说n=3与n=2结果相同,n=19与n=18结果相同,也就是只要计算一半就好了
AC代码(普通版和数据加强版都适用)
#include<bits/stdc++.h>
using namespace std;
int a[];
int main()
{
std::ios::sync_with_stdio(false);
int n;cin>>n;
if(n<=)
{
cout<<+<<endl;
return ;
}
else
{
for(int i=;i<=n+;i++)
{
if(i%==)
{
a[i]=i/;
for(int j=;j<=i/;j++)
a[i]+=a[j];
}
else
a[i]=a[i-];
}
}
if(n%==)
cout<<a[n]+<<endl;
else
cout<<a[n/*]+<<endl;
}