上午的训练结束了，THU ACM小组集体去吃午餐，他们一行N人来到了著名的十食堂。这里有两个打饭的窗口，每个窗口同一时刻只能给一个人打饭。由于每个人的口味（以及胃口）不同，所以他们要吃的菜各有不同，打饭所要花费的时间是因人而异的。另外每个人吃饭的速度也不尽相同，所以吃饭花费的时间也是可能有所不同的。
THU ACM小组的吃饭计划是这样的：先把所有的人分成两队，并安排好每队中各人的排列顺序，然后一号队伍到一号窗口去排队打饭，二号队伍到二号窗口去排队打饭。每个人打完饭后立刻开始吃，所有人都吃完饭后立刻集合去六教地下室进行下午的训练。
现在给定了每个人的打饭时间和吃饭时间，要求安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。
假设THU ACM小组在时刻0到达十食堂，而且食堂里面没有其他吃饭的同学（只有打饭的师傅）。每个人必须而且只能被分在一个队伍里。两个窗口是并行操作互不影响的，而且每个人打饭的时间是和窗口无关的，打完饭之后立刻就开始吃饭，中间没有延迟。
现在给定N个人各自的打饭时间和吃饭时间，要求输出最佳方案下所有人吃完饭的时刻。
显然吃饭慢的应该先排队,满足贪心
可以设计状态dp(l1,l2)表示队伍长度分别为l1,l2时的最短时间
但是注意到两个队伍的长度是分别变化的,所以状态应当同时维护两队的进食总时间
转移方程见代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define llint long long
using namespace std;
struct xxx{
int a,b;
bool operator < (const xxx &be)const{
return b > be.b;
}
}arr[300];
struct yyy{
int p1,p2;
}___[100000],*dp = ___ + 50000;
int main (){
int n;
cin >> n ;
for (int i = 1;i <= n;++ i)
scanf("%d%d",&arr[i].a,&arr[i].b);
sort (arr + 1,arr + 1 + n);
for (int i = -45000;i < 45000;++ i)
dp[i].p1 = dp[i].p2 = 0x3f3f3f3f;
dp[0] = yyy{0,0};
int sum_ = 0;
for (int i = 1;i <= n;++ i){
sum_ += arr[i].a;
for (int l1 = sum_;l1 >= 0;-- l1){
int l2 = sum_ - l1;
int
tmp1_p1 = max(dp[l1 - arr[i].a].p1,l1 + arr[i].b),
tmp1_p2 = dp[l1 - arr[i].a].p2,
tmp2_p1 = dp[l1].p1,
tmp2_p2 = max(dp[l1].p2,l2 + arr[i].b);
if (max(tmp1_p1,tmp1_p2) < max(tmp2_p1,tmp2_p2)){
dp[l1] = yyy{tmp1_p1,tmp1_p2};
}
else {
dp[l1] = yyy{tmp2_p1,tmp2_p2};
}
}
}
int ans = 0x3f3f3f3f;
for (int i = 0;i <= sum_;++ i)
ans = min(max(dp[i].p1,dp[i].p2),ans);
cout << ans;
return 0;
}以上.