29 lines
703 B
C++
29 lines
703 B
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
int n;
|
||
const int N = 1010;
|
||
int f[N];
|
||
|
||
int dfs(int x) {
|
||
//存在就返回
|
||
if (f[x]) return f[x];
|
||
|
||
//1就没法继续分了，同时，由于题目说：原数列不做任何修改就直接统计为一种合法数列。所以返回1
|
||
if (x == 1) return f[x] = 1;
|
||
|
||
//不是1，可以分
|
||
int ans = 1;//它自己就是一种
|
||
//在它后面不断加入[1,x/2]的数字，都可以增加方法数量
|
||
for (int i = 1; i <= x / 2; i++) ans += dfs(i);
|
||
//返回方法数量
|
||
return f[x] = ans;
|
||
}
|
||
|
||
int main() {
|
||
//输入
|
||
cin >> n;
|
||
//计算并输出
|
||
cout << dfs(n) << endl;
|
||
return 0;
|
||
} |