题面

现在有两台机器 $A$ 和 $B$ 。有 $n$ 个任务，编号 $1,2,\cdots,n$ 。你必须把每个任务安排到一台机器上处理，同时需要满足以下一些条件。

1. 你必须把每个任务安排到任意一台机器上处理。
2. 在任何时刻，一台机器只能最多处理一个任务。
3. 任务 $i(0< i\leq n)$ 可以被处理当且仅当每个任务 $j(j<i)$ 已经被完成或者正在进行。
4. 一个任务如果在一台机器上进行，它是不能被打断的。

请你算算最少完成任务的时间。

题解

设 $f_{i,j}$ 表示刚刚处理完前 $i$ 个任务时，第一台机器⽐第⼆台多 $j$ 时间的第⼀台机器最⼩花费的时间。

转移就分别考虑 $j>0$ 和 $j<0$ 的情况。

代码

const int N = 4010;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	int ta[N], tb[N];
	int f[N][N << 1];
	void minEq(int &a, int b) {a = b < a? b: a;}
	int main () {
		n = Read ();
		for (int i = 1; i <= n; i++) ta[i] = Read(), tb[i] = Read();
		memset (f, 127 / 3, sizeof f);
		const int Z = 4000;
		f[0][Z] = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= 2 * Z; j++) {
				if (j >= Z) {
					minEq(f[i][Z + ta[i]], f[i - 1][j] + ta[i]);
					minEq(f[i][j - tb[i]], f[i - 1][j]);
				} else {
					minEq(f[i][Z - tb[i]], f[i - 1][j] + Z - j);
					minEq(f[i][j + ta[i]], f[i - 1][j] + ta[i]);
				}
			}
		}
		int ans = 1 << 30;
		for (int i = 0; i <= 2 * Z; i++) minEq(ans, f[n][i] + max(0, Z - i));
		printf ("%d\n", ans);
		return 0;
	}
}

int main () {
	freopen("task.in", "r", stdin);
	freopen("task.out", "w", stdout);
	Main::main();
	return 0;
}