Link

T402161 run

Question

亮亮总共要跑 \(n\) 圈，可以分成多次，但是每次跑的圈数必须要比上一次跑的多，求跑完 \(n\) 圈的方案数

Solution

显然动态规划

定义 \(F[i][j]\) 表示一共跑了 \(i\) 圈，最后一次跑了 \(j\) 圈的方案数，转移方程就为

答案就是

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=555;
typedef long long LL;
LL F[maxn][maxn];
int main(){
	freopen("C.in","r",stdin);
	int N;
	cin>>N;
	for(int i=1;i<=N;i++){
		F[i][i]=1; 
		for(int j=1;j<i;j++){
			for(int k=j-1;k>0;k--){
				F[i][j]+=F[i-j][k];
			}
		}
	}
	LL ans=0;
	for(int i=1;i<=N;i++)
		ans+=F[N][i];
	printf("%lld\n",ans-1);
	return 0;
}