BZOJ1899或洛谷2577 [ZJOI2005]午餐

BZOJ原题链接

洛谷原题链接

解决这题得先想到一个贪心：吃饭慢的先排队。
并不会证明（感觉显然
设(f[i][j][k])表示已经排好了前(i)人，第一个队伍需要花费的打饭时间为(j)，第二个队伍需要花费的打饭时间为(k)，最后一个吃完饭的时刻。
显然这会(MLE)（滚动数组也救不了你
实际上，我们可以将(k)这一维舍去。设(S[i])表示前(i)个人打饭所需要的时间，即前缀和。
则当安排了前(i)个人，其中第一个队伍需要花费打饭的时间为(j)，那么第二个队伍所需要的打饭时间就为(S[i] - j)。
于是有状态转移方程：

(qquadqquad f[i][j] = min{ f[i][j], max{ f[i - 1][j - A[i]], j + B[i] } })

(qquadqquad f[i][j] = min{ f[i][j], max{ f[i - 1][j], S[i] - j + B[i] } })

第一个转移方程表示将第(i)个人安排至第一个队伍，最后一个吃完饭的时刻即为原本最晚吃完的和现在第(i)个人吃完饭的时刻取(max)。
第二个转移方程是将第(i)个人安排至第二个队伍，则不会对第一个队伍的打饭时间造成影响（依旧为(j)），取值同理。
(f)初始化为极大值，且(f[0][0] = 0)。
最后答案即(minlimits_{i = 0}^{S[n]}{ f[n][i] })

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 210;
struct dd{
	int x, y;
};
dd a[N];
int f[N][N * N], S[N];
inline int re()
{
	int x = 0;
	char c = getchar();
	bool p = 0;
	for (; c < '0' || c > '9'; c = getchar())
		p |= c == '-';
	for (; c >= '0' && c <= '9'; c = getchar())
		x = x * 10 + c - '0';
	return p ? -x : x;
}
inline int minn(int x, int y)
{
	return x < y ? x : y;
}
inline int maxn(int x, int y)
{
	return x > y ? x : y;
}
bool comp(dd x, dd y)
{
	return x.y > y.y;
}
int main()
{
	int i, j, n, m, mi = 1e9;
	n = re();
	for (i = 1; i <= n; i++)
	{
		a[i].x = re();
		a[i].y = re();
	}
	sort(a + 1, a + n + 1, comp);
	for (i = 1; i <= n; i++)
		S[i] = S[i - 1] + a[i].x;
	memset(f, 60, sizeof(f));
	f[0][0] = 0;
	for (i = 1; i <= n; i++)
		for (j = 0, m = S[i]; j <= m; j++)
		{
			if (j >= a[i].x)
				f[i][j] = minn(f[i][j], max(f[i - 1][j - a[i].x], j + a[i].y));
			f[i][j] = minn(f[i][j], max(f[i - 1][j], S[i] - j + a[i].y));
		}
	for (i = 0; i <= S[n]; i++)
		mi = minn(mi, f[n][i]);
	printf("%d", mi);
	return 0;
}