[文章目录]
Description
这里有两个打饭的窗口，每个窗口同一时刻只能给一个人打饭。打饭所要花费的时间是因人而异的。吃饭花费的时间也是可能有所不同的。 THU ACM小组的吃饭计划是这样的：先把所有的人分成两队，并安排好每队中各人的排列顺序，然后一号队伍到一号窗口去排队打饭，二号队伍到二号窗口去排队打饭。每个人打完饭后立刻开始吃，所有人都吃完饭后立刻集合去六教地下室进行下午的训练。 现在给定了每个人的打饭时间和吃饭时间，要求安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。 现在给定N个人各自的打饭时间和吃饭时间，要求输出最佳方案下所有人吃完饭的时刻。n<=200 ai,bi<=200
推出来了！！！开心
发现和状态有关的参数有四个！！！没错，是四个。两个队分别的总打饭时间和打完之后的吃饭时间。
对答案有贡献的只有总时间大的那个，所以可以省掉一个吃饭时间。
诶？？？当前的总打饭时间是固定的啊。。。那么第二个队的打饭时间就可以直接计算出来了。
那就可以转移了：dp[i][j]表示1~i人一个队的打饭时间为j的时候的最小的总时间。设打饭的总时间为S，那么则有：
dp[i+1][j+a]=min(max(dp[i][j],j+a+b))
dp[i+1][j]=min(max(dp[i][j],S-j+a+b))
人的排列顺序也是对答案有影响的。猜想b大的人应当放到前面，举反例发现正确。 排序+dp即可。时间复杂度n^2*a
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,dp[210][40210],ans;
struct node {int a,b;}cu[210];
bool cmp(node x,node y){return x.b>y.b;}
int main()
{
scanf("%d",&n);
memset(dp,0x3f,sizeof dp);
for(int i=1;i<=n;++i) scanf("%d%d",&cu[i].a,&cu[i].b);
sort(cu+1,cu+n+1,cmp);
dp[1][cu[1].a]=cu[1].a+cu[1].b;
dp[1][0]=cu[1].a+cu[1].b;
int S=cu[1].a,a,b;
for(int i=2;i<=n;i++)
{
a=cu[i].a; b=cu[i].b;
for(int j=1;j<=40000;j++)
{
dp[i][a+j]=min(dp[i][a+j],max(dp[i-1][j],j+a+b));
dp[i][j]=min(dp[i][j],max(dp[i-1][j],S-j+a+b));
}
S+=a;
}
ans=1<<30;
for(int j=1;j<=40000;j++)
ans=min(ans,dp[n][j]);
printf("%d",ans);
return 0;
}