PKU 1015 Jury Compromise

Jury Compromise

動的計画法の使い方がわかってきた。
D(J)-P(J) の取り得る値が高々±20nなので、m人の候補を組み合わせて D(J)-P(J)=i となりうるかどうかを表の i 番目のセルに持つ。複数ある場合は D(J)+P(J) が最大となるようにすることで、最適な組み合わせが得られる。
C++だとTime Limit Exceedで、時間オーバーに困ったときのG++でもギリギリ（954MS）。DP表の各セルにsetを持たせるのは無茶だった気もするが、まあ通ったからいいか。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

struct Juror{ int p, d; };
struct Node{ bool flag; int p, d; set<int> juror; };

int main()
{
    for ( int c=1; ; c++ )
    {
        //  input
        int n, m;
        cin >> n >> m;
        if ( n == 0  &&  m == 0 )
            break;

        vector<Juror> juror( n + 1 );
        for ( int i=1; i<=n; i++ )
            cin >> juror[i].p >> juror[i].d;

        int w = 20 * ( n + 1 );

        vector<Node> t1( 2 * w + 1 );
        vector<Node> t2( 2 * w + 1 );
        Node *score = &t1[w];
        Node *temp = &t2[w];

        //  search
        for ( int i=-w; i<=w; i++ )
            score[i].flag = false;

        score[0].flag = true;
        score[0].p = score[0].d = 0;
        
        for ( int i=0; i<m; i++ )
        {
            swap( score, temp );
            for ( int j=-w; j<=w; j++ )
                score[j].flag = false;

            for ( int j=-w; j<=w; j++ )
            if ( temp[j].flag )
            {
                for ( int k=1; k<=n; k++ )
                if ( temp[j].juror.count( k ) == 0 )
                {
                    int diff = j + juror[k].d - juror[k].p;
                    int sum = temp[j].d + temp[j].p
                              + juror[k].d + juror[k].p;

                    if ( ! score[diff].flag  ||
                         sum > score[diff].d + score[diff].p )
                    {
                        score[diff].flag = true;
                        score[diff].d = temp[j].d + juror[k].d;
                        score[diff].p = temp[j].p + juror[k].p;
                        score[diff].juror = temp[j].juror;
                        score[diff].juror.insert( k );
                    }
                }
            }
        }

        //  output
        int best = w;
        Node ans;

        for ( int i=-w; i<=w; i++ )
        if ( score[i].flag )
        {
            if ( abs(i) < best  ||
                 abs(i) == best  &&
                    score[i].p + score[i].d > ans.p + ans.d )
            {
                best = abs(i);
                ans = score[i];
            }
        }

        cout << "Jury #" << c << endl;
        cout << "Best jury has value "
             << ans.p << " for prosecution and value "
             << ans.d << " for defence:" << endl;
        for ( int i=1; i<=n; i++ )
        if ( ans.juror.count(i) > 0 )
            cout << " " << i;
        cout << endl;
        cout << endl;
    }

    return 0;
}