【问题描述】
电视里面正放着“抽百万大奖，赢幸福生活”的宣传广告，bird看后也想去试试手气，当然，作为经济学院的高材生，他可不屑只是单纯的去碰运气。经过他的一番分析，发现，商家在彩票里面做了手脚，使得每个抽奖点的中奖概率不是完全一样的，而且随着时间的变化而变化，不过这种变化是有规律的。对于第I个抽奖点，最开始的中奖概率是百万分之Pi，以后每抽一张彩票后都要重新排队，花费的时间是T分钟，每抽一次减少的概率为Di。
由于可怜的bird还有一大堆的作业没做，他只能抽出H个小时去买彩票。由于抽奖地点都在一路公共汽车的线路上，所以怕麻烦的bird决定按车站顺序抽奖，当然，bird可以从任意一站开始抽奖，对于经过的抽奖点可以买彩票，也可以不买。假设从第I个抽奖点到第I+1个抽奖点需要做Ci分钟的汽车。
Bird希望能在有限的H个小时内获得最好的运气——即抽奖的概率和最大。
[输入] 输入文件名：(tickt.in)
第一行为一个整数n，表示抽奖点的个数，1<=n<=200
第二行是两个整数H和T，1<=H<=10，1<=T<=60。
接下来的n行，每行3个整数，分别是Pi，Di，Ci（Cn=0）。1<=Pi<=10000，Di<=Pi，1<=Ci<=600。
[输出] 输出文件名：(tickt.out)
文件仅有一行，为一个整数，即抽奖概率和的最大值。
【输入输出样例】
| tickt.in | tickt.out |
| 2 1 20 200 100 10 300 200 0 | 500 |
【样例说明】
首先，bird从1号开始抽奖，花费20分钟，得到概率200，然后坐车到2号，花费10分钟，再花20分钟得到概率300，概率和是500，花费50分钟。
【评分标准】
对于每个测试点，如果你能够在规定的时间内通过每组数据，你将得到这个测试点的分数，否则，这个测试点你只能得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: