TCO2012 Round2B Medium(550) 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; }};