PKU 1014

Dividing

与えられたビー玉を組み合わせて合計の半分の価値にできるか、ということと等価。
ビー玉の価値の合計が高々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;
}