AOJ2510 Twin book report

2016/05/04 (Wed) AOJ 貪欲 DP

問題

問題文

方針

まず読み終える時間を最短にしないといけないのに注意． なのでアミもマミも全ての本を読んだ後にまとめて書くのが最適． そのときの答えは $\sum r[i] + \sum w[i]$ になる． けど，最も大きい $r[i]$ が，$\sum r[i] / 2$ より大きいとき，その戦略ができない (問題文中の図の例)． そのときは，アミは最長の本を読む→他の本を全て読む→書く，マミは最長以外の本を全て読む→間の時間に少し書く→最長の本を読む→残りを書くという戦略が最適． 間の時間になるべく無駄な時間を作らないように DP をする．これは TDPC の A 問題と似た感じでやる．

実装

#include <bits/stdc++.h>
using namespace std;

int n;
int r[1010], w[1010];

int dp[1000010];

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    while(cin >> n && n){
        int sum_r = 0, sum_w = 0, max_r = 0;
        for(int i = 0; i < n; ++i){
            cin >> r[i] >> w[i];
            if(r[max_r] < r[i]){
                max_r = i;
            }
            sum_r += r[i];
            sum_w += w[i];
        }
        if(r[max_r] * 2 <= sum_r){
            cout << sum_r + sum_w << endl;
        } else {
            swap(r[n-1], r[max_r]);
            swap(w[n-1], w[max_r]);
            int rem = r[n-1]*2 - sum_r;
            fill(dp, dp+rem+10, 0);
            dp[0] = true; // mudanazikannni tsumekomi
            for(int i = 0; i < n-1; ++i){
                for(int j = rem; j >= w[i]; --j){
                    dp[j] |= dp[j-w[i]];
                }
            }
            int dead = -1;
            for(int i = rem; i >= 0; --i){
                if(dp[i]){
                    dead = rem - i;
                    break;
                }
            }
            cout << sum_r + sum_w + dead << endl; 
        }
    }
}