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

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

我们可以设

cnt_{i}

为以

i

为第一个数时所能构造的合法数列的数量，最后的

cnt_{n}

就是答案总数。

那么怎么求

cnt_{i}

呢？我们只需让

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

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

AC Code:

CPP

#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。

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

文章操作

相关推荐

评论

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