Sum of Different Primes
2007.09.21 16:18 ACM/ICPC 2006
[問題] ACM/ICPC Asia Regional 2006 Yokohama: Problem D
[難易度] ★★☆
[解説]
動的計画法(DP)で解けます。
ナップザック問題をDPで解く仕組みを応用します。
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 番目の素数を示す)。
サンプルプログラム
[難易度] ★★☆
[解説]
動的計画法(DP)で解けます。
ナップザック問題をDPで解く仕組みを応用します。
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 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |