一道标准的题面比题目难的题

拿到题首先就是把题目翻译成我们可以读懂的亚子

求：有多少种方案使得若干个小于n的质数相加等于n

范围：n不超过200

输入数量：若干行（这绝对是个大坑，后面要考）

题目搞定了，开始分析

你看那题目前面的标签写着大大的几个字动态规划就应该知道来者不善（不会dp的可以自觉退出了）

那……就从动态规划的角度分析吧

我们的备选数字就是所有小于n的质数，可以重复利用，是完全背包

话不多说开整

#include<iostream>
using namespace std;
const int N=55;
const int M=205;
int list[N];
long long dp[N][M];
int main()
{
	int n,l=0;
	cin>>n;
	bool flag;
	for(int i=2;i<=n;i++)
	{
		flag=1;
		for(int j=2;j*j<=i;j++)
		{
			if(i%j==0)
			{
				flag=0;
				break;
			}
		}
		if(flag)
			list[++l]=i;
	}
	for(int i=1;i<=l;i++)
		dp[i][0]=1;
	for(int i=1;i<=l;i++)
	{
		for(int j=1;j<=n;j++)
		{
			dp[i][j]=dp[i-1][j];
			if(j>=list[i])
				dp[i][j]+=dp[i][j-list[i]];
		}
	}
	cout<<dp[l][n];
	return 0;
 } 

能看到这里的，应该是非常有耐心的或者交了发现问题准备找我算账的吧

别急，还记得前面输入埋下的伏笔吗，没错，这串代码只输入了一个数（想不到吧）

想输入若干个数很简单，在外面套一个好东西：

while(cin>>n)

但这个东西实在是过于未知，完全有超时的风险，但是别慌，我早就拿头试过了，没有问题的

最后还是上代码吧

#include<iostream>
using namespace std;
const int N=55;
const int M=205;
int list[N];
long long dp[N][M];
int main()
{
	int n,l=0;
	bool flag;
	while(cin>>n)
	{
		l=0;
		for(int i=2;i<=n;i++)
		{
			flag=1;
			for(int j=2;j*j<=i;j++)
			{
				if(i%j==0)
				{
					flag=0;
					break;
				}
			}
			if(flag)
				list[++l]=i;
		}
		for(int i=0;i<=l;i++)
			for(int j=0;j<=n;j++)
				dp[i][j]=0;
		for(int i=1;i<=l;i++)
			dp[i][0]=1;
		for(int i=1;i<=l;i++)
		{
			for(int j=1;j<=n;j++)
			{
				dp[i][j]=dp[i-1][j];
				if(j>=list[i])
					dp[i][j]+=dp[i][j-list[i]];
			}
		}
		cout<<dp[l][n]<<endl;
	}
	
	return 0;
 } 

但这还不够，我们很敏锐的发现，完全背包是可以压缩的，而且很简单的一种方式就是把和i有关的地方全删掉然后把没用的删掉就好了

如果不会或无法理解二维数组压缩成一维数组的可以采用双行式滚动数组

这里应为懒得改双行的，就只呈上一维数组的方法了

#include<iostream>
using namespace std;
const int N=55;
const int M=205;
int list[N];
long long dp[M];
int main()
{
	int n,l=0;
	bool flag;
	while(cin>>n)
	{
		l=0;
		for(int i=2;i<=n;i++)
		{
			flag=1;
			for(int j=2;j*j<=i;j++)
			{
				if(i%j==0)
				{
					flag=0;
					break;
				}
			}
			if(flag)
				list[++l]=i;
		}
		for(int j=0;j<=n;j++)
			dp[j]=0;
		dp[0]=1;
		for(int i=1;i<=l;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(j>=list[i])
					dp[j]+=dp[j-list[i]];
			}
		}
		cout<<dp[n]<<endl;
	}
	
	return 0;
 } 

向着星……感谢你……（无奖填空）