3132(AOJ 1269):Sum of Different Primes

PKU AOJ ICPC

keyword

動的計画法　C++

概要

整数n(<1120)、k(<14)が与えられる。このときk個の異なる素数の和がnになるような組合せの総数を求める問題。
硬貨の支払い方の問題のバリエーションの一つに過ぎない。1120以下の素数表を作っておき、dp[和がn][使った中で最大の素数(の番号)][使った素数の個数]で順に求める。厳密に計算量を考えると結構危険な気がするけど(O(n*m^2*k),mはn以下の素数の個数)、枝刈りで大分削れるのでなんとか間に合う。配列が大きいから1回RE出したけどstaticと書いて無事解決。

#define N 1120

int main(){
    ps.PB(-1);
    primeTable(N);
    static int dp[N+2][190][16];
    int i, j, k, l, n, ans, s = SZ(ps);
    REP(i,N+2)REP(j,190)REP(k,16) dp[i][j][k] = 0;
    dp[0][0][0] = 1;
    REP(i,N){
        REP(j,s+1)REP(k,15)if(dp[i][j][k]){
            for(l=j+1; l<s && i + ps[l] <= N; l++){
                dp[i+ps[l]][l][k+1] += dp[i][j][k];
            }
        }
    }

    while(scanf("%d%d",&n,&k)){
        if(!(n||k)) break;
        ans = 0;
        REP(j,190) ans += dp[n][j][k];
        printf("%d\n",ans);
    }

    return 0;
}