首页 > 代码库 > UVA 1213 Sum of Different Primes(经典dp)
UVA 1213 Sum of Different Primes(经典dp)
题意:选择k(k<15)个唯一质数,求出和为n(n<1121)的可能数
题解:预处理dp,dp[k][n]表示使用k个素数拼成n的总方案数
就是三重枚举,枚举k,枚举n,枚举小于n的素数
但是注意三重循环的顺序与位置,我们要防重防漏
第一重循环是枚举每个小于n的素数,思路是对于每个素数放入dp里面的位置
第二重倒叙枚举每个数n,倒序是类似01背包不能让枚举的素数重复加入同一个dp数组中
第三重正序枚举个数k只能放在最里面,这样才不会出现重复
import java.util.Scanner; public class Main{ static int Max = 1200; static int Maxk = 15; static long[][] dp = new long[Maxk][Max]; static int[] vis = new int[Max]; static int[] prm = new int[Max];//存所有素数 static int coun; static { for (int i = 2; i < Max; ++i) { if (vis[i] == 0) { for (int j = i + i; j < Max; j += i) { vis[j] = 1; } } } for (int i = 2; i < Max; ++i) { if (vis[i] == 0) { prm[coun++] = i; } } } private static void Init(int n) { dp[0][0]=1; // 预处理dp //注意三重循环位置,用于去重 for (int k = 0; k < coun; ++k) {//枚举每个素数 for (int j = Max-1; j >=prm[k]; --j) {//倒叙枚举每个数,类似01背包去重 for (int i = 1; i < Maxk; ++i) {//枚举个数 dp[i][j] += dp[i - 1][j - prm[k]]; } } } } public static void main(String[] args) { Init(Max); int n, k; Scanner sc = new Scanner(System.in); while (sc.hasNext()) { n = sc.nextInt(); k = sc.nextInt(); if (n + k == 0) break; System.out.println(dp[k][n]); } } }
UVA 1213 Sum of Different Primes(经典dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。