TCO2012 Round2B Medium(550) HeavyBooks

HeavyBooks

なるべく重い本から順に相手に押しつけた方が得。Tomekが最初に持ってきた本を仮定して、シミュレートすると最後にTomekとWojtekそれぞれが何番目に重い本を持っているかが分かる。あとはTomekが得するように最初に図書館から持ってくる本を決めれば良い。これは、図書館にある本軽い順にn冊の中から、m冊を選んだときにTomekが最も得をする場合を覚えて置くと、動的計画法で解ける。

#include <vector>
#include <algorithm>
#include <string>
using namespace std;

struct STATE { int T,W; };
bool operator<(STATE a,STATE b)
    { return a.W-a.T<b.W-b.T || a.W-a.T==b.W-b.T && a.W+a.T<b.W+b.T; }

class HeavyBooks{public:
vector <int> findWeight( vector <int> books, vector <int> moves )
{
    sort(books.begin(),books.end());

    vector<int> T;
    vector<int> W;

    for ( int i=0; i<(int)moves.size(); i++ )
    {
        if ( i==0 )
        {
            int m = min( moves[i], (int)books.size() );
            for ( int j=0; j<m; j++ )
                W.push_back(j);
        }
        else if ( i%2==1 )
        {
            sort(W.begin(),W.end());
            int m = min(moves[i],(int)W.size());
            for ( int j=0; j<m; j++ )
                T.push_back(W.back()),
                W.pop_back();
        }
        else
        {
            sort(T.begin(),T.end());
            int m = min(moves[i],(int)T.size());
            for ( int j=0; j<m; j++ )
                W.push_back(T.back()),
                T.pop_back();
        }
    }

    int N = (int)books.size();
    int M = min(moves[0],(int)books.size());
    string B(M,' ');
    for ( int i=0; i<(int)T.size(); i++ )
        B[T[i]] = 'T';
    for ( int i=0; i<(int)W.size(); i++ )
        B[W[i]] = 'W';

    vector<STATE> S(N+1);
    S[0].T = S[0].W = 0;
    for ( int i=1; i<=N; i++ )
        S[i].T = 100000000,
        S[i].W = 0;

    for ( int i=0; i<M; i++ )
    {
        vector<STATE> P = S;
        for ( int j=0; j<=N; j++ )
            S[j].T = 100000000,
            S[j].W = 0;

        for ( int j=0; j<=N; j++ )
        {
            for ( int k=j+1; k<=N; k++ )
            {
                STATE s = P[j];
                if ( B[i]=='T' )
                    s.T += books[k-1];
                else
                    s.W += books[k-1];
                S[k] = max( S[k], s );
            }
        }
    }

    STATE ans = *max_element(S.begin(),S.end());
    vector<int> a;
    a.push_back(ans.T);
    a.push_back(ans.W);
    return a;
}};