一开始想到贪心,按照吃饭时间长到短进行排序。
正确性显然,可以用微扰进行证明。
之后就是如何DP的事情了。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
using namespace std;
const int N=205;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;
while(c<'0'||c>'9')c=gc;
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
void qw(int x)
{
if(x/10)qw(x/10);
putchar(x%10+48);
}
int f[N][N*N],sum[N];
struct node{int a,b;bool operator <(const node a)const{return b>a.b;}}p[N];
int main()
{
int n;qr(n);
for(int i=1;i<=n;i++)qr(p[i].a),qr(p[i].b);
sort(p+1,p+n+1);
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+p[i].a;
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>=p[i].a)f[i][j]=min(f[i][j],max(f[i-1][j-p[i].a],j+p[i].b));
f[i][j]=min(f[i][j],max(f[i-1][j],sum[i]-j+p[i].b));
}
int ans=0x3f3f3f3f;
for(int i=0;i<=sum[n];i++)
ans=min(ans,f[n][i]);
qw(ans);puts("");
return 0;
}
最后一次更新于2021-02-04
0 条评论