静かで孤独な日記

のんびりたまに

AOJ 2510 Twin book report

#include<bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;
bool dp[1001][1001];

int main(){
  int n;
  while(cin>>n,n){
    vector<pair<int,int> > v;
    int sum=0,maxe=0;
    int sumw=0;
    int maxw=0;
    vector<int> vv;
    for(int i=0;i<n;i++){
      int a,b;cin>>a>>b;
      v.push_back({a,b});
      vv.push_back(b);
      sum+=a;
      if(maxe<a){
        maxe=a;
        maxw=i;
      }
      sumw+=b;
    }
    if(maxe<=sum-maxe){
      cout<<sum+sumw<<endl;
    }else{
      int ans=maxe*2+v[maxw].se;
      int nokori=maxe-(sum-maxe);
      vv.erase(vv.begin()+maxw);
      sort(vv.begin(),vv.end());
      int vvsum=0;
      for(int i=0;i<(int)vv.size();i++)vvsum+=vv[i];
      for(int i=0;i<=(int)vv.size();i++)for(int j=0;j<=nokori;j++)dp[i][j]=0;
      dp[0][0]=1;
      for(int i=0;i<(int)vv.size();i++){
        for(int j=0;j<=nokori;j++){
          if(dp[i][j]==0)continue;
          if(j+vv[i]<=nokori){
            dp[i+1][j+vv[i]]=1;
          }
          dp[i+1][j]=1;
        }
      }
      for(int i=nokori;i>=0;i--){
        if(dp[vv.size()][i]){
          cout<<ans+vvsum-i<<endl;
          break;
        }
      }
    }
  }
  return 0;
}
  • とりあえず本を早く全部読み終わりたい。
  • 本当は待たずに全部の本読みたいけど、一つだけめちゃめちゃ読むのに時間がかかる本があるとそうはいかない。
  • そんな場合は待ち時間に感想文書けば良い。
  • 待ち時間をどんなふうに使うのが一番かはdpしてあげるのが一番簡単。