HDU 2189来世一緒に歩く

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=2189
被災地にはまたn人のボランティアが来ています.震災救援指揮部は彼らをいくつかのグループに分ける必要があります.グループの数は限らないですが、グループごとに人数を素数にしなければなりません.何種類のグループ分けの方法がありますか.特别な说明:1、1つのグループしかありません;2、グループ分けの方法は人数だけに関係し、具体的な人員とは関係ない.
解題構想:この問題ビットDP問題は、01リュックサックに似ている.人数が150以内であるため,グループ化の際の人数は150以内の素数である.だから150以内の素数を先に見つけることができます.
配列b[k]で素数を保存します.動的移動方程式は、a[j+b[i]+=a[j];(a[j]すなわち人数がjであることを示すグループ化方法)

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int b[155];int k;
int main()
{
	int a[155];memset(a,0,sizeof(a));k=0;
	for(int i=2;i<=155;i++)          //  155     
	{
		if(!a[i])
		{
			b[k++]=i;
			for(int j=i+i;j<=155;j+=i)a[j]=1;
		}
	}
	memset(a,0,sizeof(a));a[0]=1;   //   
	for(int i=0;i<k;i++)
	{
		for(int j=0;j+b[i]<=150;j++)
			a[j+b[i]]+=a[j];
	}
	int n;cin>>n;
	while(n--)
	{
		int m;cin>>m;
		cout<<a[m]<<endl;
	}
}