题解：P1028 [NOIP 2001 普及组] 数的计算

· · 题解

一道水题，本蒟蒻来交一篇递推的题解。

我们可以设 cnt_{i} 为以 i 为第一个数时所能构造的合法数列的数量，最后的 cnt_{n} 就是答案总数。

那么怎么求 cnt_{i} 呢？我们只需让

cnt_{i} = \sum_{j = 1} ^ {i / 2} cnt_{j}

就可以一步一步推导出来啦！

AC Code:

#include <iostream>
using namespace std;
int n, cnt[299999];

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i / 2; j++) cnt[i] += cnt[j];       //累加cnt[1]~cnt[i / 2]
        cnt[i]++;       //不要忘了加上自己
    }
    cout << cnt[n] << ' ';
    return 0;
}

蒟蒻的第一篇题解，望管理员大大通过qwq。