【問題描述】
電視里面正放著“抽百萬大獎，贏幸福生活”的宣傳廣告，bird看后也想去試試手氣，當然，作為經(jīng)濟學院的高材生，他可不屑只是單純的去碰運氣。經(jīng)過他的一番分析，發(fā)現(xiàn)，商家在彩票里面做了手腳，使得每個抽獎點的中獎概率不是完全一樣的，而且隨著時間的變化而變化，不過這種變化是有規(guī)律的。對于第I個抽獎點，最開始的中獎概率是百萬分之Pi，以后每抽一張彩票后都要重新排隊，花費的時間是T分鐘，每抽一次減少的概率為Di。
由于可憐的bird還有一大堆的作業(yè)沒做，他只能抽出H個小時去買彩票。由于抽獎地點都在一路公共汽車的線路上，所以怕麻煩的bird決定按車站順序抽獎，當然，bird可以從任意一站開始抽獎，對于經(jīng)過的抽獎點可以買彩票，也可以不買。假設從第I個抽獎點到第I+1個抽獎點需要做Ci分鐘的汽車。
Bird希望能在有限的H個小時內(nèi)獲得最好的運氣——即抽獎的概率和最大。
[輸入] 輸入文件名：(tickt.in)
第一行為一個整數(shù)n，表示抽獎點的個數(shù)，1<=n<=200
第二行是兩個整數(shù)H和T，1<=H<=10，1<=T<=60。
接下來的n行，每行3個整數(shù)，分別是Pi，Di，Ci（Cn=0）。1<=Pi<=10000，Di<=Pi，1<=Ci<=600。
[輸出] 輸出文件名：(tickt.out)
文件僅有一行，為一個整數(shù)，即抽獎概率和的最大值。
【輸入輸出樣例】
| tickt.in | tickt.out |
| 2 1 20 200 100 10 300 200 0 | 500 |
【樣例說明】
首先，bird從1號開始抽獎，花費20分鐘，得到概率200，然后坐車到2號，花費10分鐘，再花20分鐘得到概率300，概率和是500，花費50分鐘。
【評分標準】
對于每個測試點，如果你能夠在規(guī)定的時間內(nèi)通過每組數(shù)據(jù)，你將得到這個測試點的分數(shù)，否則，這個測試點你只能得0分。
【分析】
由CEOI的釣魚改編，具體可以看《算法藝術與信息學競賽》P13。
1: #include <stdio.h>
2: #include <iostream>
3: #define maxn 210
4: using namespace std;
5:
6: int b[maxn][maxn];
7: int p[maxn],d[maxn],c[maxn];
8: int h,t,tot;
9: struct ss
10: {
11: int pi,di;
12: } hp[maxn];
13: int remain,ans,teans,n;
14:
15: void down(int x)
16: {
17: int te=2*x;
18: while (te<=tot)
19: {
20: if ((te+1<=tot)&&(hp[te].pi<hp[te+1].pi)) ++te;
21: if (hp[x].pi>hp[te].pi) break;
22: swap(hp[x],hp[te]);
23: x=te;
24: te=x*2;
25: }
26: }
27:
28: int main()
29: {
30: freopen("ticket.in","r",stdin);
31: freopen("ticket.out","w",stdout);
32:
33: scanf("%d%d%d",&n,&h,&t);
34: h*=60;
35: for (int i=1;i<=n;++i) scanf("%d%d%d",&p[i],&d[i],&c[i]);
36: for (int i=1;i<=n;++i)
37: for (int j=i+1;j<=n;++j)
38: b[i][j]=b[i][j-1]+c[j-1];
39: for (int i=1;i<=n;++i)
40: for (int j=n;j>=i;--j)
41: {
42: teans=0;
43: remain=h-b[i][j];
44: memset(hp,0,sizeof(hp));
45: for (int k=1;k<=j-i+1;++k)
46: {
47: hp[k].pi=p[i+k-1];
48: hp[k].di=d[i+k-1];
49: }
50: tot=j-i+1;
51: for (int k=j-i+1;k>=1;--k) down(k);
52: while ((remain>=t)&&(hp[1].pi>0))
53: {
54: teans+=hp[1].pi;
55: hp[1].pi-=hp[1].di;
56: remain-=t;
57: down(1);
58: }
59: if (teans>ans) ans=teans;
60: }
61: printf("%d\n",ans);
62: return 0;
63: }
64: