[洛谷]P1028 数的计算

相关标签 动态规划

题目简叙

思路

找规律

s=0 n=1 0; s=1 n=1 1;
s=2 n=2 exm:12,2,s=3 n=2 exm:13,1;
s=4 n=4 exm:14,13,24,124;s=5 n=4 exm:15,25,125,5;
s=5 n=3

观察发现：
if n%2==1 ansN=ansN-1
else ansN+=ansN(N/2)

代码

#include <iostream>

using namespace std;
const int N=1e4;
int f[N];
int main()
{
    f[1]=1;
    int n;
    cin>>n;
    for(int i=2;i<=n;i++)
        if(i%2==1)f[i]=f[i-1];
        else f[i]=f[i-1]+f[i/2];
    
    cout<<f[n];
    return 0;
}

AC记录