当前位置 博文首页 > ApocalypseTq的博客:P1028 [NOIP2001 普及组] 数的计算 题解
以前一直很肤浅的认为这道题就是纯靠模拟就解决了。
如今学了DP了,细细思考,原来是可以用递推来解决的。
思路:
递推到i个数的解,
就是枚举第i个数的二分之一到0
初始化呢, 就是f[0]=0;
这道题可以归于 用DP求方案数类型。
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int maxn=1000+2;
int n;
int f[maxn];
int main()
{
scanf("%d",&n);
f[0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=i/2;j++)
f[i]+=f[j];
printf("%d\n",f[n]);
return 0;
}
cs