PKU 1014
与えられたビー玉を組み合わせて合計の半分の価値にできるか、ということと等価。
ビー玉の価値の合計が高々120000ということに着目して動的計画法で解く。価値m以下のビー玉を組み合わせて価値iを作れるかどうかを表に持つ。そのまま実装すると制限時間をオーバーしてしまうので、一工夫している。↓のソースのforループ内で flag[p] == m が成り立つならば、以降マークできる箇所は既にマークされているはず。
#include <iostream> #include <vector> #include <algorithm> #include <functional> using namespace std; int main() { for ( int c=1; ; c++ ) { int marble[7]; for ( int i=1; i<=6; i++ ) cin >> marble[i]; if ( find_if( marble+1, marble+7, bind2nd(not_equal_to<int>(),0) ) == marble + 7 ) break; int sum = 0; for ( int i=1; i<=6; i++ ) sum += i * marble[i]; bool divide; if ( sum % 2 == 0 ) { int n = sum / 2; // the value "i" can be composed of marbles of value <= flag[i] vector<int> flag( n+1, 999 ); flag[0] = 0; for ( int m=1; m<=6; m++ ) { for ( int i=n; i>=0; i-- ) if ( flag[i] < m ) { for ( int j = 0, p = i; j <= marble[m] && p <= n && flag[p] != m; j++, p += m ) flag[p] = m; } } divide = flag[n] <= 6; } else { divide = false; } cout << "Collection #" << c << ":" << endl; cout << "Can" << ( divide ? "" : "'t" ) << " be divided." << endl; cout << endl; } return 0; }