AOJ 2510: 双子の読書感想文
解法
本を読む時間を最短にしないといけないことに注目します。とりあえず感想を書かなければならないことは忘れて, 読むことだけを考えましょう。
ある一冊の本(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; }