PE 114~117 (全是dp)

PE 114

代码：

#include<bits/stdc++.h>using namespace std;long long dp[60];//dp[i]表示从左边某个位置 开始 到位置 i 是红块的方案数 long long solve(int n){	memset(dp,0,sizeof dp); 	long long ans=0; 	for(int i=3;i<=n;i++)	{		dp[i]=i-2;				for(int j=3;j<=i-4;j++)		{			dp[i]+=(dp[j]*(i-j-3));		}		PRintf("dp[%d]=%lld/n",i,dp[i]); 		ans+=dp[i];	}	ans++; //唯一一种全是黑块的 	return ans;}int main(){	cout<<solve(7)<<endl;	cout<<solve(50)<<endl;	return 0;}
PE 115
代码：
#include<bits/stdc++.h>using namespace std;long long dp[1000];//dp[i]表示从左边某个位置 开始 到位置 i 是红块的方案数 long long solve(int n){	memset(dp,0,sizeof dp); 	long long ans=0; 	for(int i=50;i<=n;i++)	{		dp[i]=i-49;				for(int j=50;j<=i-51;j++)		{			dp[i]+=(dp[j]*(i-j-50));		}	//	printf("dp[%d]=%lld/n",i,dp[i]); 		ans+=dp[i];	}	ans++; //唯一一种全是黑块的 	return ans;}int main(){		for(int i=51;;i++)	{		if(solve(i)>=1000000)		{			cout<<"ans="<<i<<endl;			break;		}	}//	cout<<solve(7)<<endl;//	cout<<solve(50)<<endl;	return 0;}
PE 116代码：
#include<bits/stdc++.h>using namespace std;long long dp[1000][1000];long long solve(int m,int n){    if(m>n)return 1;    if(n<0)return 0;    if(n==0)return 1;    if(dp[m][n]>0)return dp[m][n];    return  dp[m][n]= solve(m,n-1)+solve(m,n-m);}int main(){	memset(dp,0,sizeof(dp));	cout<<solve(2,5)-1<<endl;	cout<<solve(3,5)-1<<endl;	cout<<solve(4,5)-1<<endl;	cout<<"example = "<<solve(2,5)+solve(3,5)+solve(4,5)-3<<endl;	cout<<endl;	cout<<solve(2,50)-1<<endl;	cout<<solve(3,50)-1<<endl;	cout<<solve(4,50)-1<<endl;	cout<<"ans = "<<solve(2,50)+solve(3,50)+solve(4,50)-3<<endl;	return 0;}PE 117
代码：
#include<bits/stdc++.h>using namespace std;long long dp[1000]={0};//f(n)=f(n-1)+f(n-2)+f(n-3)+f(n-4)long long solve(int n){	if(n<0) return 0;	if(n==0)return 1;	if(dp[n]>0)return dp[n];	return  dp[n]= solve(n-1)+solve(n-2)+solve(n-3)+solve(n-4);}int main(){	cout<<solve(5)<<endl;	cout<<solve(50)<<endl;	return 0;}