AOJ 2510 - Twin Book Report

問題文 : 双子の読書感想文

解法 :

場合分けを行って考える.

• 最も本を読む時間が, その他の本を読む時間の総和より長い場合

この場合はアミが最も長い本を読んでいる間に, マミがそれ以外の全ての本を読み終わっているので, その間に生じた時間でいくつかの感想文をかける. 間に生じる時間はたかだか1000 であるから, $T \leqq 1000$ として$O(NT)$ 時間のDP で感想文を書ける時間の最大値を求めれば良い. 感想文を書けずに余った時間 + (本を読むのにかかる時間+感想を書くのにかかる時間) の総和 が求める答えである.

• そのような本がない場合

この場合はアミが先に最も長い本から読み始め, その本を読み終わった段階で, マミが2 冊目(以降)の本を読んでいるので追っかけるように本を読むことで, (本を読むのにかかる時間+感想を書くのにかかる時間) の総和で全ての本が読める.

コード

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int N;
	
	while (scanf("%d", &N) && N){
		pair<int, int> a[1024];
		for (int i = 0; i < N; i++){
			scanf("%d %d", &a[i].first, &a[i].second);
		}
		
		sort(a, a + N);
		
		int sum = 0, ans = 0;
		for (int i = 0; i < N - 1; i++) sum += a[i].first;
		for (int i = 0; i < N; i++) ans += a[i].first + a[i].second;
		
		if (sum >= a[N - 1].first){
			printf("%d\n", ans);
		}
		else {
			bool dp[1001] = {false};
			dp[0] = true;
			int spend = 0;
			for (int i = 0; i < N - 1; i++){
				for (int j = a[N - 1].first - sum; j >= a[i].second; j--){
					dp[j] |= dp[j - a[i].second];
					if (dp[j]) spend = max(spend, j);
				}
			}
			printf("%d\n", ans + a[N - 1].first - sum - spend);
		}
	}
	
	return (0);
}