题目

代码

#include<bits/stdc++.h>
using namespace std;
int ans=0;
const int N=1e3+10;
long long dp[N][N];
void dp1(int n,int m){
	memset(dp,0,sizeof dp);
	dp[0][0]=1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=min(i,m);++j)
			dp[i][j]=dp[i-1][j-1]+dp[i-j][j];
	return ;
}
void dp2(int n,int p){
	memset(dp,0,sizeof dp);
	for(int i=0;i<=p;++i)
		dp[0][i]=1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=p;++j){
			dp[i][j]=dp[i][j-1];
			if(i-j>=0)
				dp[i][j]+=dp[i-j][j-1];
		}
	return ;
}
void dp3(int n,int p){
	memset(dp,0,sizeof dp);
	for(int i=0;i<=p;++i)
		dp[0][i]=1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=p;++j){
			//dfs5(n,p-2)+dfs5(n-p,p);
			if(j>=2)
				dp[i][j]=dp[i][j-2];
			if(i-j>=0)
				dp[i][j]+=dp[i-j][j];
		}
	return ;
}
int main(){
	//freopen("test.in","r",stdin);
	int n,m,ans,t;
	while(~scanf("%d %d",&n,&m)){
		dp1(n,m);
		printf("%lld\n",dp[n][m]);
		dp2(n,n);
		printf("%lld\n",dp[n][n]);
		t=n;
		if(t%2==0) 
			--t;
		dp3(n,t);
		printf("%lld\n",dp[n][t]);	
	}
	return 0;
}

dp解法，TLE