土下座しながら探索中

主に競技プログラミング

AOJ 2510 : Twin book report

問題リンク:Twin book report | Aizu Online Judge

問題概要:
日本語なので略

・自分が読み落としていた文
> 加えて,本の返却期限が近いため,まずはなるべく早くすべての本を読み終えるようにしてもらう事にした
つまり、読める本があるなら感想文よりもそちらを読むほうを優先しなければならない

解法:
動的計画法
基本的には先に全て本を読んでからまとめて感想文を全て書く
しかし、一番読むのに時間がかかる本のその時間が他の本を全て読むのにかかる時間よりも長い場合はその空いた時間をうまく活用しなくてはならない
なので、動的計画法でその空いた時間にできる限りたくさんの感想文を書く
上に書いた一文を読み落とさないように


コード:

struct Book
{
  int read,write;
  Book(int read=inf,int write=inf):read(read),write(write){}
  bool operator < (const Book& a)const
  {
    if(read != a.read)return read < a.read;
    return write < a.write;
  }
};

int main()
{
  int N;
  while(scanf("%d",&N),N)
    {
      Book array[N];
      int sum_r = 0;
      int sum_w = 0;
      rep(i,N)
	{
	  scanf("%d %d",&array[i].read,&array[i].write);
	  sum_r += array[i].read;
	  sum_w += array[i].write;
	}

      sort(array,array+N);

      if(sum_r-array[N-1].read < array[N-1].read)
	{
	  int limit = array[N-1].read - (sum_r-array[N-1].read);
	  bool dp[limit+1];
	  rep(i,limit+1)dp[i] = false;
	  dp[0] = true;
	  int mex = 0;
	  rep(i,N-1)for(int j=limit;j>=0;j--)
	    {
	      if(!dp[j] || j+array[i].write > limit)continue;
	      dp[j+array[i].write] = true;
	      mex = max(mex,j+array[i].write);
	    }
	  printf("%d\n",sum_r+sum_w+(limit-mex));
	}
      else
	{
	  printf("%d\n",sum_r+sum_w);
	}

    }
  return 0;
}