首先第一反应该是贪心，对于同一队列中的人应该是吃时间长的人先打饭更优，因为打饭时间不可避免，同时吃饭的人更多就一定更优，接下来就是处理谁在哪队了，设$f[i][j][k]$为前i人队1花费j时间队2花费k时间全部吃完用的最小时间，然而其实不用因为j+k为全集，所以搞个前缀和可以减一维，
转移为$f[i][j]=min(f[i][j],max(f[i-1][j-a[i].a], j+a[i].b),max(f[i-1][j], sum[i]-j+a[i].b))$，
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=209; int n; int f[maxn][maxn*maxn],sum[maxn]; struct node{ int a,b; bool operator <(const node&t)const{ return b>t.b||(b==t.b&&a<t.a); } }a[maxn]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d%d",&a[i].a,&a[i].b),sum[i]=sum[i-1]+a[i].a; sort(a+1,a+1+n); memset(f,0x3f,sizeof(f)); f[0][0]=0; for(int i=1;i<=n;i++) for(int j=0;j<=sum[i];j++){ if(j>=a[i].a)f[i][j]=min(f[i][j],max(f[i-1][j-a[i].a],j+a[i].b)); f[i][j]=min(f[i][j],max(f[i-1][j],sum[i]-j+a[i].b)); } int ans=1e9; for(int i=0;i<=sum[n];i++) ans=min(ans,f[n][i]); printf("%d\n",ans); }
原文：https://www.cnblogs.com/superminivan/p/11671476.html