Coder Space

PKU 3132 Sum of Different Primes ---01背包

题意：给出n，k，要求计算n==k个素数的和的情况有几种。

解法：01背包问题。筛出素数到prime[ ]中，n<=1120, k <= 14打表. dp[i][n][k]表示用前i个素数，选k个和为n的方法数
          dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-prime[i]][k-1]，根据“背包九讲”空间可优化为dp[j][k]。


 

源代码

posted on 2010-12-01 17:01 David Liu 阅读(101) 评论(0)  编辑 收藏 引用 所属分类: 动态规划


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


My Links

Blog Stats

常用链接

留言簿

文章分类

文章档案

搜索

最新评论