质数和分解（背包型DP） 解题日志

质数和分解（prime）

【问题描述】

任何大于 1 的自然数 N，都可以写成若干个大于等于2且小于等于 N 的质数之和表达式(包括只有一个数构成的和表达式的情况)，并且可能有不止一种质数和的形式。例如9 的质数和表达式就有四种本质不同的形式：9 = 2+5+2 = 2+3+2+2 = 3+3+3 = 2+7 。

这里所谓两个本质相同的表达式是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。试编程求解自然数 N 可以写成多少种本质不同的质数和表达式。

【输入文件】（prime.in）：

文件中的每一行存放一个自然数 N , 2≤N≤200。

【输出文件】（prime.out）：

依次输出每一个自然数 N 的本质不同的质数和表达式的数目。

【样例输入】

2

【样例输出】

1

【样例输入】

200

【样例输出】

9845164

#include<bits/stdc++.h>
using namespace std;
bool pflag[300];
int n;
int f[300][300];
void prime(int maxn){
	for(int i=0;i<=maxn;i++){
		pflag[i]=true;
	}
	pflag[0]=pflag[1]=false;
	for(int i=2;i<=maxn;i++){
		if(pflag[i]){
			for(int j=i*2;j<=maxn;j+=i){
				pflag[j]=false;
			}
		}
	}
}

int chai(int n,int minn){
	if(f[n][minn]!=-1){
		//cout<<"( "<<n<<" , "<<minn<<" ) = "<<f[n][minn]<<endl;
		return f[n][minn];
	}
	if(n<minn){
		f[n][minn]=0;
		//cout<<"< ( "<<n<<" , "<<minn<<" ) = "<<f[n][minn]<<endl;
		return 0;
	}
	if(n==minn){
		f[n][minn]=1;
		//cout<<"= ( "<<n<<" , "<<minn<<" ) = "<<f[n][minn]<<endl;
		return 1;
	}/*
	if(n>minn && n<2*minn){
		f[n][minn]=0;
		cout<<"~ ( "<<n<<" , "<<minn<<" ) = "<<f[n][minn]<<endl;
		return 0;
	}*/
	f[n][minn]=0;
	if(pflag[n]) f[n][minn]=1;
	for(int i=minn;i<=n;i++){
		if(pflag[i]){
			f[n][minn]+=chai(n-i,i);
		}
	}
	//cout<<"R ( "<<n<<" , "<<minn<<" ) = "<<f[n][minn]<<endl;
	return f[n][minn];
}

int main(){
	memset(f,-1,sizeof(f));
	prime(200);
	cin>>n;
	cout<<chai(n,2);
	return 0;
}