UVA 1213 - Sum of Different Primes（递推）

类似一个背包问题的计数问题。（虽然我也不记得这叫什么背包了

一开始我想的状态定义是：f[n = 和为n][k 个素数]。

递推式呼之欲出： f[n][k] = sigma f[n-p][k-1]。

但是题目还有一个要求是不同素数之和，为了保证素数不同，那就先枚举素数吧，

f[i][n][k] = sigma  f[i-1][n-p][k-1]，

然后滚动数组降掉一维就好了。

本地筛一遍发现maxn 范围内素数数量是pi_n = 187。

maxn*maxk*pi_n ≈ 1e6。

复杂度也是没问题哒。

/*********************************************************

*      --------------Crispr---------------               *

*   author AbyssalFish                                   *

**********************************************************/

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = , maxk = ;

int f[maxn+][maxk+];

const int pi_n = ;

bool vis[maxn+];

int pm[pi_n];

void sieve(int n = maxn)

{

    int m = sqrt(n+0.5);

    for(int i = ; i <= m; i++){

        if(!vis[i])

        for(int j = i*i; j <= n; j += i) vis[j] = ;

    }

    int k = ;

    for(int i = ; i <= n; i++){

        if(!vis[i]){

            pm[k] = i;

            k++;

        }

    }

    //cout<<k;

}

void init()

{

    sieve();

    f[][] = ;

    for(int i = ; i < pi_n; i++){

        int p = pm[i];

        for(int n = maxn; n >= p; n--){

            for(int k = ; k <= maxk; k++){

                f[n][k] += f[n-p][k-];

                //if(f[n][k] < 0) cout<<"over flow"<<endl;

            }

        }

    }

}

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    init();

    int n,k;

    while(scanf("%d%d",&n,&k),n){

        printf("%d\n",f[n][k]);

    }

    return ;

}