题目背景
Noip2001普及组第一题。
题目描述
我们要求找出具有下列性质数的个数(包括输入的自然数n)。先输入一个自然数n(n≤1000),然后对此自然数按照如下方法进行处理:
(1)不作任何处理;
(2)在它的左边加上一个自然数,但该自然数不能超过原数的一半;
(3)加上数后,继续按此规则进行处理,直到不能再加自然数为止。
输入格式
输入一个自然数 n(n≤1000)。
输出格式
输出一个整数,即满足条件的数。
样例数据 1
输入
6
输出
6
备注
【样例说明】
满足条件的数为:
6
16
26
126
36
136
水题一发,递推一下就知道了……其实是练习下动态数组!
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#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; } |