PE 114~117 (全是dp)

╰半夏微凉° 2022-07-12 07:38 146阅读 0赞

[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;
    }

[PE 114]: https://projecteuler.net/problem=114
[PE 115]: https://projecteuler.net/problem=115
[PE 116]: https://projecteuler.net/problem=116
[PE 117]: https://projecteuler.net/problem=117