洛谷p2577-zjoi2005-午餐

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,ans;
struct  {
 int a,b;
    
 //b 吃饭时间 
}t[222]; 
bool cmp(lunch p,lunch q)
{
 return p.b>q.b;
}
int dp[400040],s[1010],sum;
//表示 
int main()
{
   scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&t[i].a,&t[i].b);
  sort(t+1,t+n+1,cmp);
 memset(dp,0x3f,sizeof(dp));
   dp[0]=0;
 for(int i=1;i<=n;i++)  s[i]=s[i-1]+t[i].a;
  for(int i=1;i<=n;i++) {
     for(int j=sum;j>=0;j--) {
           dp[j+t[i].a]=min(dp[j+t[i].a],max(dp[j],t[i].b+j+t[i].a));
           dp[j]=max(dp[j],t[i].b+s[i]-j);
      }
        sum+=t[i].a;
 }
    ans=2147483647;
  for(int i=1;i<=sum;i++) ans=min(ans,dp[i]);
 printf("%dn",ans);
 return 0;
}