次元传送门：洛谷P2577
思路
首先贪心是必须的
我们能感性地理解出吃饭慢的必须先吃饭（结合一下生活）
因此我们可以先按吃饭时间从大到小排序
然后就能自然地想到用f[i][j][k]表示前i个人在第一个窗口排队用了j时间 在第二个窗口排队用了k时间
然后就自然地炸空间了
所以我们要降维
因为我们可以由第一个窗口推出第二个窗口所用时间 所以我们可以改原来的数组为：
f[i][j]表示前i个人 在第一个窗口用了j时间 得到的所有前i个人吃完饭的最短时间
如何用第一个窗口推出第二个窗口呢？
显而易见 第一个窗口排队用了j时间+第二个窗口排队用了k时间为前i个人排队用的总时间
那么我们可以用前缀和维护一个总时间sum[i]表示前i个人用的总时间
那么k=sum[i]-j 解决
状态转移方程：
f[i][j]=min(f[i][j],max(f[i-
1][j-p[i].a],j+p[i].b));
//第i个人在第一窗口
//f[i-1][j-p[i].a]表示第i个人排队+吃饭的时间比第i-1个人短 所以不影响
//j+p[i].b即有影响 前i个人排队时间+第i个人吃饭时间
f[i][j]=min(f[i][j],max(f[i-
1][j],sum[i]-j+p[i].b));
//第i个人在第二窗口
//同理 sum[i]-j=k即第二个窗口排队总时间
代码
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 220
#define INF 1e9+7
struct P
{
int a;
int b;
}p[maxn];
int n;
int sum[maxn];
int f[maxn][maxn*
maxn];
bool cmp(P a,P b)
{
return a.b>
b.b;
}
int main()
{
memset(f,0x3f,
sizeof(f));
cin>>
n;
for(
int i=
1;i<=n;i++) cin>>p[i].a>>
p[i].b;
sort(p+
1,p+
1+n,cmp);
//排序
for(
int i=
1;i<=n;i++) sum[i]=sum[i-
1]+p[i].a;
//前缀和
f[
0][
0]=
0;
//初始化
for(
int i=
1;i<=n;i++)
//枚举第几个人
for(
int j=
0;j<=sum[i];j++)
//枚举排队时间
{
if(j>=p[i].a) f[i][j]=min(f[i][j],max(f[i-
1][j-p[i].a],j+
p[i].b));
f[i][j]=min(f[i][j],max(f[i-
1][j],sum[i]-j+
p[i].b));
}
int ans=
INF;
for(
int i=
0;i<=sum[n];i++)
//查询时间
ans=
min(ans,f[n][i]);
cout<<
ans;
}
转载于:https://www.cnblogs.com/BrokenString/p/9913146.html
相关资源：JAVA上百实例源码以及开源项目
