https://www.luogu.com.cn/problem/P1806
题目描述
路人甲准备跑n圈来锻炼自己的身体，他准备分多次（>1）跑完，每次都跑正整数圈，然后休息下再继续跑。
为了有效地提高自己的体能，他决定每次跑的圈数都必须比上次跑的多。
可以假设他刚开始跑了 0 圈，那么请问他可以有多少种跑完这 n 圈的方案？
输入格式
一行一个整数，代表 n。
输出格式
一个整数表示跑完这 n 圈的方案数。
输入 #1
212
输出 #1
995645335
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=1e5+10,M=4023;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
LL n,f[N];
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
LL T=1;
//cin>>T;
while(T--)
{
cin>>n;
f[0]=1;//赋初值
for(int i=1;i<=n;i++)//跑了i圈
{
for(int j=n;j>=i;j--)//后面可以加多少圈，是建立在我之前最后跑的那圈的基础上的
{
f[j]+=f[j-i];
}
}
cout<<f[n]-1<<endl;
}
return 0;
}