ZJOI2005 午餐
题目 ID ： 2422
时间限制: 1000ms
空间限制: 262144kB
题目入口：https://www.xinyoudui.com/ac/contest/774001BB400041602548D16/problem/2422
算法： 贪心dp 。
解题思路：
吃饭慢的先打饭可以节省时间，所以先按吃饭时间降序排序，剩下的问题就是如何把同学分配到两队。
dp_{i,j,k} 表示前 i 位同学，一队排队时间为 j ，另一队排队时间为 k 时的总时间。但由于数据为不超过 200 的整数， 200^3=8000000 ，会导致内存过大。由于 j+k 的值是前 i 人总打饭时间，可以优先处理打饭时间的前缀和， k=sum_i-j 所以：
定义： dp_{i,j} 表示前 i 位同学，一对排队时间为 j 时的总打饭时间。
循环： i为1\sim n ， j为0\sim sum_i 。
动态转移方程：
if(j>=s_{i.a})dp_{i,j}=min(dp_{i,j},max(dp_{i-1,j-s_{i.a}},j+s_{i.b}));
将第 i 为同学放在第 1 队。
如果第 i 位同学的加入每有影响总时间： dp_{i-1,j-s_{i.a}} 。
如果第 i 位同学的吃饭时间+总排队时间>加入前的总时间（即影响总时间）： j+s_{i.b} 。
dp_{i,j}=min(dp_{i,j},max(dp_{i-1,j},sum_i-j+s_{i.b}));
将第 i 位同学放在第 2 队。
sum_i-j 为 2 队排队时间。
struct node
{int a,b;
}s[N];
bool cmp(node a,node b)
{return a.b>b.b;
}
int sum[N];
int dp[N][N*N];void solve()
{int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>s[i].a>>s[i].b;sort(s+1,s+n+1,cmp);
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+s[i].a;memset(dp,127,sizeof(dp));
dp[0][0]=0;for(int i=1;i<=n;i++)
for(int j=0;j<=sum[i];j++)
{if(j>=s[i].a)dp[i][j]=min(dp[i][j],max(dp[i-1][j-s[i].a],j+s[i].b));
dp[i][j]=min(dp[i][j],max(dp[i-1][j],sum[i]-j+s[i].b));}
int res=dp[n][0];
for(int i=1;i<=sum[n];i++)res=min(res,dp[n][i]);cout<<res;
}
