(ZJU-2008再試験)-HSJ-1881-卒業bg(DP)

卒業する
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2015    Accepted Submission(s): 741
Problem Description
毎年卒業シーズンになると卒業生が大喜びし、親友が食事を約束し、ネット上では「bg」と呼ばれている.異なる団体に参加するbgは異なる感覚を持ち、bgごとに「快楽度」を非負の整数で定義することができる.各bgの楽しさ、持続時間、bgの発起人の離校時間をリストするbgリストを指定します.bgの一連の時間を手配して、自分が最大の楽しさを得ることができます.
例えば4試合bg:
第1回の楽しみ度は5で、1時間続き、発起人は1時間後に離れなければならない.
2回目の楽しみ度は10で、2時間続き、発起人は3時間後に離れなければならない.
第3回の楽しみ度は6で、1時間続き、発起人は2時間後に離れなければならない.
4回目の楽しみ度は3で、1時間続き、発起人は1時間後に離れなければならない.
最大の快楽度を得る手配は、まず3回目を始め、快楽度6を獲得し、1時間目に終わり、発起人も離れることができる.2回目を再開し、快楽度10を獲得し、3時間目に終了すると、発起人はちょうど離れることができた.発起人はもう学校を離れたので、他のbgを手配することはできません.そのため、最大の楽しみ度は16です.
bgは発起人が離れる前に終わらなければならないことに注意してください.途中でbgを離れてはいけません.途中でbgを入れてはいけません.
また、あなたの人気があまりにも良いので、30人の団体bgがいるかもしれません.そのため、このスケジュールの問題を解決するためにプログラムを書く必要があります.
 
 
Input
テスト入力には、いくつかのテスト例が含まれます.各試験例の第1行は整数N(<=30)を含み、その後、N行があり、各行はbgの情報を与える.
h l t
このうちhは快楽度,lは持続時間(時間),tは発起人離校時間である.データ保証lは、発起人がt時間後に離れなければならない場合、bgは主人が離れる前に終わらなければならないため、tより大きくない.
Nが負数の場合は入力が終了します.
 
 
Output
各試験例の出力は1行を占め,最大快楽度を出力する.
 
 
Sample Input

3
6 3 3
3 2 2
4 1 3
4
5 1 1
10 2 3
6 1 2
3 1 1
-1

 
 
Sample Output

7
16

 
  
m[i][j]   i bg    j         
  
m[i][j]=max{ m[i-1][j],  m[i-1][j-bg[i].l]+bg[i].h  },    j-bg[i].l>=0 && j<=bg[i].t
  
m[0][j]=m[i][0]=0;
  
      max{m[n][0]~m[n][mmax]}
  
 
  
bg                bg      ，         t   
  
bg                     mmax
  
#include  #include  using namespace std; int m[31][1000]; struct bg_typ { int h,l,t; }; bg_typ bg[31]; bool cmp(const bg_typ a,const bg_typ b) { return a.t>n&&n>=0) { int mmax=0; for(int t=1;t<=n;++t) { cin>>bg[t].h>>bg[t].l>>bg[t].t; if(bg[t].t>mmax) mmax=bg[t].t; } sort(bg+1,bg+n+1,cmp); for(int i=0;i<=n;++i)m[i][0]=m[0][i]=0; for(int i=1;i<=n;++i) { for(int j=0;j<=mmax;++j) { if(j<=bg[i].t&&j-bg[i].l>=0) m[i][j]=max(m[i-1][j],m[i-1][j-bg[i].l]+bg[i].h); else m[i][j]=m[i-1][j]; } } int result=m[n][mmax]; for(int j=mmax;j>=0;--j) if(result