[Zjoi2004]Lunch 午餐

Time Limit:3000MS  Memory Limit:65536K
Total Submit:13 Accepted:9
Case Time Limit:1000MS

Description

上午的训练结束了，THU ACM小组集体去吃午餐，他们一行N人来到了著名的十食堂。这里有两个打饭的窗口，每个窗口同一时刻只能给一个人打饭。由于每个人的口味（以及胃口）不 同，所以他们要吃的菜各有不同，打饭所要花费的时间是因人而异的。另外每个人吃饭的速度也不尽相同，所以吃饭花费的时间也是可能有所不同的。
THU ACM小组的吃饭计划是这样的：先把所有的人分成两队，并安排好每队中各人的排列顺序，然后一号队伍到一号窗口去排队打饭，二号队伍到二号窗口去排队打 饭。每个人打完饭后立刻开始吃，所有人都吃完饭后立刻集合去六教地下室进行下午的训练。
现在给定了每个人的打饭时间和吃饭时间，要求安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。
假设THU ACM小组在时刻0到达十食堂，而且食堂里面没有其他吃饭的同学（只有打饭的师傅）。每个人必须而且只能被分在一个队伍里。两个窗口是并行操作互不影响 的，而且每个人打饭的时间是和窗口无关的，打完饭之后立刻就开始吃饭，中间没有延迟。
现在给定N个人各自的打饭时间和吃饭时间，要求输出最佳方案下所有人吃完饭的时刻。

Input

第一行一个整数N，代表总共有N个人。
以下N行，每行两个整数 Ai，Bi。依次代表第i个人的打饭时间和吃饭时间。

Output

一个整数T，代表所有人吃完饭的最早时刻。

Sample Input

5
2 2
7 7
1 3
6 4
8 5

Sample Output

17

Hint

方案如下：

窗口1： 窗口2：
7 7 1 3
6 4 8 5
2 2

【限制】
所有输入数据均为不超过200的正整数。

Source

额。这个题目还不错。。挺有意思的。。
首先一看到这经典的模型，可以B大的要在前面。。
然后就可以动归了。。
先按B降序排序。。
用Dp[i][j]表示前i个，第一个队的吃饭时间和为j的最优值。。
Code：
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=201;
using namespace std;
int A[maxn],B[maxn],P[maxn],n;
bool cmp(int i,int j)
{
return B[i]>B[j];
}
int Dp[2][maxn*maxn];
inline void Update(int&t,int c)
{
if(t==-1||t>c)t=c;
}
int main()
{
//freopen("in","r",stdin);
cin>>n;
rep(i,n)
{
cin>>A[i]>>B[i];
P[i]=i;
}
sort(P,P+n,cmp);
int now=0,next=1,sum=0;
memset(Dp[next],-1,sizeof Dp[next]);
Dp[next][0]=0;
for(int i=0;i<n;i++)
{
int t=P[i],c,first,second,nc;
swap(now,next);
memset(Dp[next],-1,sizeof Dp[next]);
rep(j,sum+1)
if((c=Dp[now][j])!=-1)
{
first=j;
second=sum-j;
//Put it In First Queue
nc=max(first+A[t]+B[t],c);
Update(Dp[next][j+A[t]],nc);
//Put it In Second Queue
nc=max(second+A[t]+B[t],c);
Update(Dp[next][j],nc);
}
sum+=A[t];
}
int ans=inf;
rep(i,sum+1)if(Dp[next][i]!=-1)ans=min(ans,Dp[next][i]);
cout<<ans<<endl;
}