首页 > 代码库 > hdu 2189 来生一起走（DP）
hdu 2189 来生一起走（DP）
题意：
有N个志愿者。指挥部需要将他们分成若干组，但要求每个组的人数必须为素数。问不同的方案总共有多少。（N个志愿者无差别，即每个组的惟一标识是：人数）
思路：
假设N个人可分为K组，将这K组的人数从小到大排序，num1，...，numk。
故N个人分组的方案数dp[n]=sum(dp[numk]) （所有分为K组的不同方案的和）
代码：
bool yes[155];int prime[155];int dp[155];int main(){ mem(yes,true); int C = 0; rep(i,2,150){ if(yes[i]==true){ prime[++C] = i; for(int j=i;j<=150;j+=i){ yes[j] = false; } } } mem(dp,0); dp[0]=1; rep(k,1,C){ for(int i=0;i+prime[k]<=150;++i) dp[i+prime[k]] += dp[i]; } int T; cin>>T; while(T--){ int n; cin>>n; cout<<dp[n]<<endl; } return 0;}
hdu 2189 来生一起走（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。