【NOIP 2001普及组第一题数的计数】

2015年6月4日 0条评论 929次阅读 0人点赞

题目背景

Noip2001普及组第一题。

题目描述

我们要求找出具有下列性质数的个数（包括输入的自然数n）。先输入一个自然数n（n≤1000），然后对此自然数按照如下方法进行处理：
（1）不作任何处理；
（2）在它的左边加上一个自然数，但该自然数不能超过原数的一半；
（3）加上数后，继续按此规则进行处理，直到不能再加自然数为止。

输入格式

输入一个自然数 n（n≤1000）。

输出格式

输出一个整数，即满足条件的数。

样例数据 1

输入

输出

备注

【样例说明】
满足条件的数为：
6
16
26
126
36
136

水题一发，递推一下就知道了……其实是练习下动态数组！

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<vector>
using namespace std;
int n;
int main()
{
	//freopen("test.in", "r", stdin);
	//freopen("test.out", "w", stdout);
	scanf("%d", &n);
	vector<int> ans(n + 1);
	ans[1] = 1;
	for (int i = 2; i <= n; i++)
	{
		for (int j = 1; j <= i / 2; j++)
			ans[i] += ans[j];
		ans[i]++;
	}
	cout << ans[n] << endl;
	return 0;
}