首页 > 代码库 > 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)