【問(wèn)題描述】
電視里面正放著“抽百萬(wàn)大獎(jiǎng)，贏幸福生活”的宣傳廣告，bird看后也想去試試手氣，當(dāng)然，作為經(jīng)濟(jì)學(xué)院的高材生，他可不屑只是單純的去碰運(yùn)氣。經(jīng)過(guò)他的一番分析，發(fā)現(xiàn)，商家在彩票里面做了手腳，使得每個(gè)抽獎(jiǎng)點(diǎn)的中獎(jiǎng)概率不是完全一樣的，而且隨著時(shí)間的變化而變化，不過(guò)這種變化是有規(guī)律的。對(duì)于第I個(gè)抽獎(jiǎng)點(diǎn)，最開(kāi)始的中獎(jiǎng)概率是百萬(wàn)分之Pi，以后每抽一張彩票后都要重新排隊(duì)，花費(fèi)的時(shí)間是T分鐘，每抽一次減少的概率為Di。
由于可憐的bird還有一大堆的作業(yè)沒(méi)做，他只能抽出H個(gè)小時(shí)去買(mǎi)彩票。由于抽獎(jiǎng)地點(diǎn)都在一路公共汽車(chē)的線路上，所以怕麻煩的bird決定按車(chē)站順序抽獎(jiǎng)，當(dāng)然，bird可以從任意一站開(kāi)始抽獎(jiǎng)，對(duì)于經(jīng)過(guò)的抽獎(jiǎng)點(diǎn)可以買(mǎi)彩票，也可以不買(mǎi)。假設(shè)從第I個(gè)抽獎(jiǎng)點(diǎn)到第I+1個(gè)抽獎(jiǎng)點(diǎn)需要做Ci分鐘的汽車(chē)。
Bird希望能在有限的H個(gè)小時(shí)內(nèi)獲得最好的運(yùn)氣——即抽獎(jiǎng)的概率和最大。
[輸入] 輸入文件名：(tickt.in)
第一行為一個(gè)整數(shù)n，表示抽獎(jiǎng)點(diǎn)的個(gè)數(shù)，1<=n<=200
第二行是兩個(gè)整數(shù)H和T，1<=H<=10，1<=T<=60。
接下來(lái)的n行，每行3個(gè)整數(shù)，分別是Pi，Di，Ci（Cn=0）。1<=Pi<=10000，Di<=Pi，1<=Ci<=600。
[輸出] 輸出文件名：(tickt.out)
文件僅有一行，為一個(gè)整數(shù)，即抽獎(jiǎng)概率和的最大值。
【輸入輸出樣例】
| tickt.in | tickt.out |
| 2 1 20 200 100 10 300 200 0 | 500 |
【樣例說(shuō)明】
首先，bird從1號(hào)開(kāi)始抽獎(jiǎng)，花費(fèi)20分鐘，得到概率200，然后坐車(chē)到2號(hào)，花費(fèi)10分鐘，再花20分鐘得到概率300，概率和是500，花費(fèi)50分鐘。
【評(píng)分標(biāo)準(zhǔn)】
對(duì)于每個(gè)測(cè)試點(diǎn)，如果你能夠在規(guī)定的時(shí)間內(nèi)通過(guò)每組數(shù)據(jù)，你將得到這個(gè)測(cè)試點(diǎn)的分?jǐn)?shù)，否則，這個(gè)測(cè)試點(diǎn)你只能得0分。
【分析】
由CEOI的釣魚(yú)改編，具體可以看《算法藝術(shù)與信息學(xué)競(jìng)賽》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: