UVa 1213 – Sum of Different Primes [数学+DP]

点击打开vjudge题目链接

题意:给定n和k,求选择k个不同素数组成n的种数。

分析:先打好素数表,然后DP递推即可。因为素数是不同的,所以要注意递推时循环的内外次序。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1200;
bool checked[maxn] = {1, 1};
int pri[maxn], tot, dp[maxn][15];
void getPrime() {
    for(int i = 2; i < maxn; ++i) {
        if(!checked[i]) pri[tot++] = i;
        for(int j = 0; j < tot && pri[j] * i < maxn; ++j) {
            checked[pri[j]*i] = true;
            if(!(i % pri[j])) break;
        }
    }
}

void init() {
    memset(dp, 0, sizeof(dp)); dp[0][0] = 1;
    for(int i = 0; i < tot; ++i) {
        int cur = pri[i];
        for(int j = maxn-1; j >= cur; --j) {
            for(int k = 1; k <= 14; ++k) {
                dp[j][k] += dp[j-cur][k-1];
            }
        }
    }
}

int main() {
    getPrime(); init();
    int n, k;
    while(cin >> n >> k, n||k)
        cout << dp[n][k] << endl;
    return 0;
}

欢迎留言