当前位置 博文首页 > ApocalypseTq的博客:P1028 [NOIP2001 普及组] 数的计算 题解

    ApocalypseTq的博客:P1028 [NOIP2001 普及组] 数的计算 题解

    作者:[db:作者] 时间:2021-09-23 15:40

    以前一直很肤浅的认为这道题就是纯靠模拟就解决了。

    如今学了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