AOJ 2510: 双子の読書感想文

問題

Twin book report | Aizu Online Judge

解法

本を読む時間を最短にしないといけないことに注目します。とりあえず感想を書かなければならないことは忘れて, 読むことだけを考えましょう。

ある一冊の本(A とする)を読むのにかかる時間が, 他のすべての本を読む時間の合計よりも長い場合, A 以外の本から読み始めた人は, もう一方が A を読み終わるまで, 暇な時間が出来ます。よって, 本を 2 人が読み終わるのにかかる時間は 2*(Aを読む時間) です。

上記の A のような本がない場合は, 同時並行で二人がまだ読んでない本を読めるので, 2 人が本を読み終わるのにかかる時間は, (本を読む時間の合計) です。

以上の 2 通りの場合分けを考えれば, 感想を書かなければならない場合も簡単にわかります。
2 つ目の場合では, 全部読み終える -> 全部感想を書くを 2 人が同時並行にできるので, かかる時間は sum(読む時間+感想書く時間) です。
1 つ目の場合は, 一方の人が A を読み終えるまでに, 少しでも多くの時間を使って感想を書きたいです。これは dp[N][T] = (N 冊目までで T 時間使って感想を書き終えられるか) というのを簡単な dp で求めれば最高どれだけの時間を A が読み終えられる前に書けるかがわかるので解を得られます。

const int MAXN = 1024;
pii P[MAXN];
bool dp[2][MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    while (cin >> N) {
        if (N==0) break;
        for (int i = 0; i < N; i++) cin >> P[i].first >> P[i].second;
        sort(P, P+N);
        int sum = 0;
        for (int i = 0; i < N-1; i++) sum += P[i].first;
        if (sum >= P[N-1].first) {
            int ans = 0;
            for (int i = 0; i < N; i++) ans += P[i].first+P[i].second;
            cout << ans << endl;
        } else {
            int diff = P[N-1].first - sum;
            memset(dp, false, sizeof(dp));
            dp[0][0] = true;
            for (int i = 0; i < N-1; i++) {
                int cur = i%2, tar = cur^1;
                for (int j = 0; j <= diff; j++) {
                    if (!dp[cur][j]) continue;
                    dp[tar][j] |= true;
                    int t = j+P[i].second;
                    if (t <= diff) dp[tar][t] |= true;
                }
            }
            int wsum = 0;
            for (int i = 0; i < N; i++) wsum += P[i].second;
            int t = diff;
            for (; t > 0; t--) if (dp[(N-1)%2][t]) break;
            cout << 2*P[N-1].first + (wsum-t) << endl;
        }
    }
    return 0;
}