简单DP+贪心

Code:

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<set>

#include<algorithm>

#include<map>

#include<vector>

#include<queue>

#include<iostream>

#include<string>

#include<cmath>

#define FOR(i,a,b) for(i=(a);i<=(b);i++)

#define ROF(i,a,b) for(i=(a);i>=(b);i--)

#define N 210

typedef long long LL;

using namespace std;

struct node{int a,b;};

int cmp(node a,node b)

{return a.b>b.b;}

node c[N];

int f[N][N*N],sum[N];

int main()

{

int i,j,n;

scanf("%d",&n);

FOR(i,1,n) scanf("%d %d",&c[i].a,&c[i].b);

sort(c+1,c+1+n,cmp);

FOR(i,1,n) sum[i]=sum[i-1]+c[i].a;

memset(f,0x5f,sizeof(f));

f[0][0]=0;

FOR(i,0,n-1) FOR(j,0,sum[i])

{

int tmp=max(f[i][j],j+c[i+1].a+c[i+1].b);

f[i+1][j+c[i+1].a]=min(f[i+1][j+c[i+1].a],tmp);

tmp=max(f[i][j],sum[i]-j+c[i+1].a+c[i+1].b);

f[i+1][j]=min(f[i+1][j],tmp);

}

int ans=2E9;

FOR(i,0,sum[n]) if (f[n][i]<ans) ans=f[n][i];

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

}

Views: 361 | Added by: dhy0077 | Rating: 5.0/1

Only registered users can add comments.
[ Sign Up | Login ]

Clever Space