luogu 2577 [ZJOI2005]午餐 贪心+dp

Code: 

#include <bits/stdc++.h>
#define N 201
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
struct P
{
    int a,b;
    P(int a=0,int b=0):a(a),b(b){}
}s[N];
int f[N][N*N],sum[N];
bool cmp(P a,P b)
{
    return a.b>b.b;
}
int main()
{
    // setIO("input");
    int n,i,j,k;
    scanf("%d",&n);
    for(i=1;i<=n;++i) scanf("%d%d",&s[i].a,&s[i].b);
    sort(s+1,s+1+n,cmp);
    for(i=1;i<=n;++i) sum[i]=sum[i-1]+s[i].a;
    memset(f,127,sizeof(f));
    f[0][0]=0;
    for(i=1;i<=n;++i)
    {
        for(j=0;j<=sum[i];++j)
        {
            if(j>=s[i].a)
            {
                f[i][j]=min(f[i][j], max(f[i-1][j-s[i].a], j+s[i].b));
            }
            f[i][j]=min(f[i][j], max(f[i-1][j], sum[i]-j+s[i].b));
        }
    }
    int ans=1000000000;
    for(i=1;i<=sum[n];++i)
    {
        ans=min(ans, f[n][i]);
    }
    printf("%d\n",ans);
    return 0;
}