P2577 [ZJOI2005]午餐

首先可以数学地证明：可对所有人按吃饭时间从大到小排序

然后会想到表示前个人,一队用时间打饭，另一队用时间打饭的最小用时。

思想就是知道，就可以保证没有后效性。

但数组开不下，这时发现,便可以去掉以为一维。

还有要注意的就是初始化的问题了。

#include<algorithm>
#include<iostream>
#include<cstdio>
int read();
#define inf 2000000000
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int maxn=220;
int maxx(int a,int b){return a<b?b:a;}
int miin(int a,int b){return a>b?b:a;}
struct Ren{
    int a,t;
    bool operator < (const Ren &b)const{
        return t>b.t;
    }
}ren[maxn];


int n,s[maxn],f[maxn][maxn*maxn];
int main(){
    cin>>n;
    rep(i,1,n)cin>>ren[i].a>>ren[i].t;
    sort(ren+1,ren+n+1);
    s[0]=0;
    rep(i,1,n)s[i]=s[i-1]+ren[i].a;
    rep(i,0,n)
    rep(a,0,(i==n)?(s[i]):(s[i+1]))
    f[i][a]=inf;
    f[0][0]=0;
    rep(i,1,n)
    rep(a,0,s[i]){
        f[i][a]=miin(f[i][a],maxx(f[i-1][a],s[i]-a+ren[i].t));
        if(a>=ren[i].a)
        f[i][a]=miin(f[i][a],maxx(f[i-1][a-ren[i].a],a+ren[i].t));
    }
    int Ans=inf;
    rep(a,0,s[n])Ans=miin(Ans,f[n][a]);
    cout<<Ans;
}
int read(){
    int s=0,k=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')k=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*k;
}