luogu2577/bzoj1899 午餐 (貪心+dp)

首先，應該盡量讓吃飯慢的排在前面，先按這個排個序

然后再來決定每個人到底去哪邊

設f[i][j]是做到了第i個人，然后1號窗口目前的總排隊時間是j，目前的最大總時間

有這個i和j的話，再預處理出前i個人的排隊總時間sum[i]，可以知道在2號窗口的排隊時間是sum[i]-j

拿著兩個去更新答案就行了

#include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=210;

inline ll rd(){
    ll x=0;char c=getchar();int neg=1;
    while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*neg;
}

int f[maxn][maxn*maxn],st[maxn];
int N;
struct Node{
    int e,q;
}p[maxn];

inline bool cmp(Node a,Node b){return a.e>b.e;}

int main(){
    //freopen("","r",stdin);
    int i,j,k;
    N=rd();
    for(i=1;i<=N;i++){
        p[i].q=rd(),p[i].e=rd();
    }sort(p+1,p+N+1,cmp);
    for(i=1;i<=N;i++)
        st[i]=st[i-1]+p[i].q;
    
    CLR(f,127);f[0][0]=0;
    for(i=1;i<=N;i++){
        for(j=0;j<=N*200;j++){
            if(f[i-1][j]>=1e8) continue;
            f[i][j+p[i].q]=min(f[i][j+p[i].q],max(f[i-1][j],j+p[i].q+p[i].e));
            f[i][j]=min(f[i][j],max(f[i-1][j],st[i]-j+p[i].e));
        }
    }
    int ans=1e9;
    for(j=0;j<=N*200;j++)
        ans=min(ans,f[N][j]);
    printf("%d\n",ans);
    return 0;
}

?