Sum of Different Primes

[問題] ACM/ICPC Asia Regional 2006 Yokohama: Problem D

[難易度]　★★☆

[解説]

動的計画法（ＤＰ）で解けます。
ナップザック問題をＤＰで解く仕組みを応用します。

T[i][j][k]　を

1 ～ i 番目の素数のうち k 個を用いて j を表す組み合わせの数

とすると、

T[i][j][k] = T[i-1][j][k] + T[i-1][j-primes[i]][k-1]

となります（primes[i]は i 番目の素数を示す）。

サンプルプログラム

001 #include<iostream>
002 #include<vector>
003 using namespace std;
004 #define PMAX 187
005 #define NMAX 1120
006 #define KMAX 14
007 
008 int T[PMAX+1][NMAX+1][KMAX+1];
009 
010 void eratos ( int n, vector<int> &p){
011     bool prime[NMAX+1];
012     for ( int i = 0; i <= n; i++ ) prime[i] = false;
013     for ( int i = 3; i <= n; i += 2 ) prime[i] = true;
014     prime[2] = true;
015     for ( int i = 3; i*i <= n; i += 2 ){
016         if ( !prime[i] ) continue;
017         for ( int j = i + i; j <= n; j += i ) prime[j] = false;
018     }
019     for ( int i = 0; i <= n; i++ ) if ( prime[i] ) p.push_back(i);
020 }
021 
022 void initialize(){
023     vector<int> primes;
024     eratos( NMAX, primes );
025     
026     for ( int i = 0; i < PMAX; i++ ){
027         for ( int j = 0; j <= NMAX; j++ ){
028             for ( int k = 0; k <= KMAX; k++ ) T[i][j][k] = 0;
029             if ( j == primes[i] ) T[i][j][1] = 1;
030         }
031     }
032     
033     for ( int i = 1; i < PMAX; i++ ){
034         for ( int j = 0; j <= NMAX; j++ ){
035             for ( int k = 1; k <= KMAX; k++ ){
036                 T[i][j][k] += T[i-1][j][k];
037                 if ( j - primes[i] >= 0 ) {
038                     T[i][j][k] += T[i-1][j-primes[i]][k-1];
039                 }
040             }
041         }
042     }
043 }
044 
045 main(){
046     initialize();
047     int n, k;
048     while( cin >> n >> k, (n || k) ) cout << T[PMAX-1][n][k] << endl;
049 }