洛谷 P1028 [NOIP2001 普及组] 数的计算

题目

https://www.luogu.com.cn/problem/P1028

思路

使用f[i]，代表数i的情况。怎么产生f[i]呢？根据题意，数的左边可以由小于等于原数的一半的数拼接。
这样的话，f[i]就等于小于等于i/2的所有数的可能加起来，还要加1（数可以是自己本身不改变）。

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#define ll long long
using namespace std;

ll f[1010];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i/2;j++){
            f[i]+=f[j];
        }
        f[i]++;
    }
    cout<<f[n]<<endl;
    return 0;
}