【BZOJ1899】午餐（动态规划）

题面

BZOJ

题解

我太弱了

这种\(dp\)完全做不动。。

首先，感性理解一些

如果所有人都要早点走，

那么，吃饭时间长的就先吃

吃饭时间短的就晚点吃

所以，按照吃饭时间排序

我们不难得出一个每个人吃完饭的时间

之和前面所有人的打饭的时间和有关

所以

\(f[i][j][k]\)表示当前做到第\(i\)个人，第一列，第二列前面的人的打饭时间之和分别为\(j,k\)时，最后一个人吃完饭的最小时间

因为人的顺序我们是知道的

所以\(j+k\)是一个定值，是所有人打饭时间的前缀和

因此我们只需要记录其中一个

所以，状态是\(f[i][j]\)表示当前做到第\(i\)个人，

第一列队伍前面所有人打饭的时间和是\(j\)时

最后一个人吃完饭的最小时间

如果把这个人放在第一列

\(f[i][j]=min(f[i][j],max(f[i-1][j-Get[i]],j+eat[i]))\)

这个应该不难理解

另外一个，把这个人放在第二列

\(f[i][j]=max(f[i-1][j],sum[i]-j+eat[i])\)

这题应该是一个很显然的\(dp\)

但是我却做不出来

我果然太弱了

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 210

inline int read()

{

	int x=0,t=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=-1,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return x*t;

}

struct Peo{int a,b;}p[MAX];

int s[MAX],ans=2e9;

int f[MAX][MAX*MAX],n;

bool operator<(Peo a,Peo b)

{

	if(a.b!=b.b)return a.b>b.b;

	else return a.a>b.a;

}

int main()

{

	n=read();

	for(int i=1;i<=n;++i)p[i].a=read(),p[i].b=read();

	sort(&p[1],&p[n+1]);

	for(int i=1;i<=n;++i)s[i]=s[i-1]+p[i].a;

	memset(f,63,sizeof(f));

	f[0][0]=0;

	for(int i=1;i<=n;++i)

	{

		for(int j=s[i-1];j>=0;--j)

		{

			f[i][j+p[i].a]=min(f[i][j+p[i].a],max(f[i-1][j],j+p[i].a+p[i].b));

			f[i][j]=max(f[i-1][j],s[i-1]-j+p[i].a+p[i].b);

		}

	}

	for(int i=0;i<=s[n];++i)ans=min(f[n][i],ans);

	printf("%d\n",ans);

	return 0;

}