#
【描述】
“汉诺塔”，是一个众所周知的古老游戏。现在我们把问题稍微改变一下：如果一共有4根柱子，而不是3根，那么至少需要移动盘子多少次，才能把所有的盘子从第1根柱子移动到第4根柱子上呢？
为了编程方便，您只需要输出这个结果mod 10000的值。
【输入】
一个正整数n。（0<n<=50000）
【输出】
一个正整数，表示把n个盘子从第1根柱子移动到第4根柱子需要的最少移动次数mod 10000的值。
【样例输入】
15
【样例输出】
129
【分析】
弄出前几个数，发现规律。
f[1]=1，之后分别是加2个2，加3个4，加4个8，加5个16……
1: #include <stdio.h>
2: #define maxn 50010
3:
4: int a,b;
5: int k=1,t;
6: long long j=1;
7: int n;
8:
9: int main()
10: {
11: freopen("hnoi.in","r",stdin);
12: freopen("hnoi.out","w",stdout);
13:
14: scanf("%d",&n);
15: b=1;
16: for (int i=2;i<=n;++i)
17: {
18: a=b;
19: if (!t)
20: {
21: t=++k;
22: j*=2;
23: j%=10000;
24: }
25: b=(a+j)%10000;
26: --t;
27: }
28: printf("%d\n",b);
29: return 0;
30: }
31:
【试题描述】
小FF的第一片矿区已经开始运作了， 他着手开展第二片矿区……
小FF的第二片矿区， 也是”NewBe_One“计划的核心部分， 因为在这片矿区里面有全宇宙最稀有的两种矿物，科学家称其为NEW矿和BE矿。
矿区是被划分成一个n*m的矩形区域。 小FF探明了每一小块区域里的NEW矿和BE矿的蕴藏量， 并且小FF还在矿区的北边和西边分别设置了NEW矿和BE矿的收集站。你的任务是设计一个管道运输系统，使得运送的NEW矿和BE矿的总量最多。
管道的型号有两种，一种是东西向，一种是南北向。在一个格子内你能建造一种管道，但丌能两种都建。如果两个同类型管道首位相接，它们就可以被连接起来。
另外这些矿物都十分丌稳定，因此它们在运送过程中都丌能拐弯。这就意味着如果某个格子上建有南北向管道，但是它北边的格子建有东西向管道，那么这根南北向管道内运送的任何东西都将丢失。迚一步地，运到NEW矿收集站的BE矿也会丢失，运到BE矿收集站的NEW矿也会丢失。
【输入格式】
第一行包含两个整数n和m，表示矿区大小。
以下n行，每行m个整数，其中第i行第j个整数G[ i , j ] 描述各个格子上的BE矿数量。接下来以类似的矩阵表示各个格子上的NEW矿数量。
【输出格式】
仅一个整数， 表示最多可以采集到的NEW矿和BE矿的总量。
【输入样例】
4 4
0 0 10 9
1 3 10 0
4 2 1 3
1 1 20 0
10 0 0 0
1 1 1 30
0 0 5 5
5 10 10 10
【输出样例】
98
【数据范围】
对于30%的数据： 0<= n，m <=100;
对于100%的数据： 0<= n, m <=1000;
0<= G[ i, j ] <=1000.
【分析】
每个点只有两种状态，放be的管道或者放new的管道。
1: #include <stdio.h>
2: #include <iostream>
3: #define maxn 1010
4: using namespace std;
5:
6: int g[maxn][maxn][2];
7: long long f[maxn][maxn][2];
8: int ne[maxn][maxn],be[maxn][maxn];
9: int n,m;
10:
11: int main()
12: {
13: freopen("industry.in","r",stdin);
14: freopen("industry.out","w",stdout);
15:
16: scanf("%d%d",&n,&m);
17: for (int i=1;i<=n;++i)
18: for (int j=1;j<=m;++j)
19: scanf("%d",&g[i][j][0]);
20: for (int i=1;i<=n;++i)
21: for (int j=1;j<=m;++j)
22: scanf("%d",&g[i][j][1]);
23: for (int i=1;i<=n;++i)
24: for (int j=1;j<=m;++j)
25: {
26: ne[i][j]=ne[i-1][j]+g[i][j][1];
27: be[i][j]=be[i][j-1]+g[i][j][0];
28: }
29: for (int i=1;i<=n;++i)
30: for (int j=1;j<=m;++j)
31: {
32: f[i][j][0]=be[i][j]+max(f[i-1][j][0],f[i-1][j][1]);
33: f[i][j][1]=ne[i][j]+max(f[i][j-1][1],f[i][j-1][0]);
34: }
35: printf("%lld\n",max(f[n][m][1],f[n][m][0]));
36: return 0;
37: }
38:
【描述】
中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了，他们各派出N匹马，每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢取最多的钱？
【输入】
第一行为一个正整数n (n <= 2000) ，表示双方马的数量。
第二行有N个整数表示田忌的马的速度。
第三行的N个整数为齐王的马的速度。
【输出】
仅有一行，为田忌赛马可能赢得的最多的钱，结果有可能为负。
【样例输入】
3
92 83 71
95 87 74
【样例输出】
200
【分析】
如果齐王的马是按速度排序之后，从高到低被派出的话，田忌一定是将他马按速度排序之后，从两头取马去和齐王的马比赛。
n设f[i,j]表示齐王按从强到弱的顺序出马和田忌进行了i场比赛之后，从“头”取了j匹较强的马，从“尾”取了i-j匹较弱的马，所能够得到的最大盈利。
n状态转移方程如下：
nF[I,j]=max{f[i-1,j]+g[n-(i-j)+1,i],f[i-1,j-1]+g[j,i]}
n其中g[i,j]表示田忌的马和齐王的马分别按照由强到弱的顺序排序之后，田忌的第i匹马和齐王的第j匹马赛跑所能取得的盈利，胜为200，输为－200，平为0。
1: #include <stdio.h>
2: #include <limits.h>
3: #include <stdlib.h>
4: #define maxn 1010
5:
6: int a[maxn],b[maxn];
7: int g[maxn][maxn];
8: int f[2][maxn];
9: int n,er;
10: int ans;
11:
12: int cmp(const void*a,const void*b)
13: {
14: int c=*(int*)a,d=*(int*)b;
15: if (c<d) return 1;
16: if (c>d) return -1;
17: return 0;
18: }
19:
20: int main()
21: {
22: scanf("%d",&n);
23: for (int i=1;i<=n;++i) scanf("%d",&b[i]);
24: for (int i=1;i<=n;++i) scanf("%d",&a[i]);
25: a[0]=b[0]=INT_MAX;
26: qsort(a,n+1,sizeof(int),cmp);
27: qsort(b,n+1,sizeof(int),cmp);
28: for (int i=1;i<=n;++i)
29: for (int j=1;j<=n;++j)
30: if (a[i]>b[j]) g[i][j]=-200;
31: else
32: if (a[i]<b[j]) g[i][j]=200;
33: for (int i=1;i<=n;++i)
34: {
35: er^=1;
36: for (int j=0;j<=i;++j)
37: {
38: f[er][j]=f[er^1][j]+g[i][n-i+j+1];
39: if (j)
40: if (f[er^1][j-1]+g[i][j]>f[er][j])
41: f[er][j]=f[er^1][j-1]+g[i][j];
42: }
43: }
44: for (int i=0;i<=n;++i)
45: if (f[er][i]>ans)
46: ans=f[er][i];
47: printf("%d\n",ans);
48: return 0;
49: }
50:
今天上午讲的是线性的动归。讲的例题有：
- 机器分配模型
- 船
- 楼梯问题
- 田忌赛马
- 最长公共子串
然后就是有关矩形的动态规划。如下：
- 滑雪
- 工业时代
还有区间类的：
- 凸多边形划分
- 最大乘积
- 石子合并（用到了四边形不等式）
- 数字游戏
然后有三道测试题：
- 四塔问题
- 关灯
- 任务安排
下午开始将树形的动态规划。
- 聚会的快乐
- 三色二叉树
- 皇宫看守
- 珠宝
- 符文之旅（最小与最大）
没有写的题目以后会逐步完成。
【问题描述】
一棵二叉树可以按照如下规则表示成一个由0、1、2 组成的字符序列，我们称之为“二叉树序列S”：
2表示该树有两个子节点， 和分别表示其两个子树的二叉树序列
1表示该树有一个子节点， 为其子树的二叉树序列
0表示该树没有子节点
你的任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。
【输入文件】
输入文件名：TRO.IN
输入文件仅有一行，不超过10000 个字符，表示一个二叉树序列。
【输出文件】
输出文件名：TRO.OUT
输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被
染成绿色。
【样例输入】
1122002010
【样例输出】
5 2
【分析】
1.动归分析
拿最大来说。
每个节点的状态只有三种颜色，我们用f[i][0],f[i][1]分别代表第i个点染绿色和不然绿色的最多的点数。因为如果一个点不染绿色，那么他染另两种颜色是等价的。如此我们就得到了如下的动规方程：
- 叶子：f[i][0]=1; f[i][1]=0;
- 一个子节点：f[i][0]=f[子节点][1]; f[i][1]=max(f[子节点][0],f[子节点][1]);
- 两个子节点：f[i][0]=f[左儿子][1]+f[右儿子][1]; f[i][1]=max(f[左儿子][1]+f[右儿子][0],f[左儿子][0]+f[右儿子][1]);
最后输出就是max(f[0][1],f[0][0])。
最小的和最大的相同。
2.树的确定
因为是一棵二叉树的前序遍历，那么对于一个有子节点的点来说，左儿子就是i+1。我们引进一个link[i]，表示以i为根的子树最后一个点的标号，那么r[i]=link[l[i]]+1。
对于link[l]，我们如此确定：
- 叶子：link[l]=l;
- 一个子节点：link[l]=link[l+1];
- 两个子节点：link[l]=link[link[l+1]+1];
然后就是实现了。因为自己弄得还是不是很熟，打了两节课。
1: #include <stdio.h>
2: #include <string.h>
3: #include <iostream>
4: #define maxn 10010
5: #define MAXINT 10000000
6: using namespace std;
7:
8: char s[maxn];
9: int f[maxn][2];
10: int link[maxn];
11: int n;
12: int l[maxn],r[maxn];
13:
14: int _find(int x)
15: {
16: if (link[x]) return link[x];
17: if (s[x]=='0') link[x]=x;
18: else
19: if (s[x]=='1') link[x]=_find(x+1);
20: else
21: link[x]=_find(_find(x+1)+1);
22: return link[x];
23: }
24:
25: void find1(int x)
26: {
27: if (f[x][0]) return;
28: if (s[x]=='0')
29: {
30: f[x][0]=1;
31: f[x][1]=0;
32: }
33: else
34: if (s[x]=='1')
35: {
36: find1(l[x]);
37: f[x][0]=f[l[x]][1]+1;
38: f[x][1]=max(f[l[x]][1],f[l[x]][0]);
39: }
40: else
41: {
42: find1(l[x]);
43: find1(r[x]);
44: f[x][0]=f[l[x]][1]+f[r[x]][1]+1;
45: f[x][1]=max(f[l[x]][1]+f[r[x]][0],f[l[x]][0]+f[r[x]][1]);
46: }
47: }
48:
49: void find2(int x)
50: {
51: if (f[x][0]<MAXINT) return;
52: if (s[x]=='0')
53: {
54: f[x][0]=1;
55: f[x][1]=0;
56: }
57: else
58: if (s[x]=='1')
59: {
60: find2(l[x]);
61: f[x][0]=f[l[x]][1]+1;
62: f[x][1]=min(f[l[x]][1],f[l[x]][0]);
63: }
64: else
65: {
66: find2(l[x]);
67: find2(r[x]);
68: f[x][0]=f[l[x]][1]+f[r[x]][1]+1;
69: f[x][1]=min(f[l[x]][1]+f[r[x]][0],f[l[x]][0]+f[r[x]][1]);
70: }
71: }
72:
73: int main()
74: {
75: freopen("tro.in","r",stdin);
76: freopen("tro.out","w",stdout);
77:
78: scanf("%s",s);
79: n=strlen(s);
80: _find(0);
81: for (int i=0;i<n;++i)
82: {
83: l[i]=i+1;
84: r[i]=link[l[i]]+1;
85: }
86: find1(0);
87: printf("%d ",max(f[0][0],f[0][1]));
88: for (int i=0;i<n;++i)
89: f[i][0]=f[i][1]=MAXINT;
90: find2(0);
91: printf("%d\n",min(f[0][0],f[0][1]));
92: return 0;
93: }
94:
题目网上都可以找到。
注意初始化s[i][j]的时候要加上100000而不是10！！！我傻叉子了= =
1: #include <stdio.h>
2: #define MAXINT 10000000
3: #define maxn 200
4:
5: int f[maxn][maxn][maxn][2];//0 max|||| 1 min
6: int s[maxn][maxn];
7: int a[maxn];
8: int n,m;
9: int maxans,minans=MAXINT;
10:
11: void find(int x,int y,int t)
12: {
13: if (f[x][y][t][0]) return;
14: if (t==1)
15: {
16: f[x][y][1][0]=f[x][y][1][1]=s[x][y];
17: return;
18: }
19: for (int k=x+t-1-1;k<y;++k)
20: {
21: find(x,k,t-1);
22: if (f[x][k][t-1][1]*s[k+1][y]<f[x][y][t][1]) f[x][y][t][1]=f[x][k][t-1][1]*s[k+1][y];
23: if (f[x][k][t-1][0]*s[k+1][y]>f[x][y][t][0]) f[x][y][t][0]=f[x][k][t-1][0]*s[k+1][y];
24: }
25: }
26:
27: int main()
28: {
29: freopen("game.in","r",stdin);
30: freopen("game.out","w",stdout);
31:
32: scanf("%d%d",&n,&m);
33: for (int i=1;i<=n;++i)
34: {
35: scanf("%d",&a[i]);
36: a[i+n]=a[i];
37: }
38: for (int i=1;i<=2*n;++i)
39: for (int j=i;j<=2*n;++j)
40: for (int k=1;k<=m;++k)
41: f[i][j][k][1]=MAXINT;
42: for (int i=1;i<=2*n;++i)
43: for (int j=i;j<=2*n;++j)
44: s[i][j]=(s[i][j-1]+a[j]+100000)%10;
45: for (int i=1;i<=n;++i) find(i,i+n-1,m);
46: for (int i=1;i<=n;++i)
47: {
48: if (f[i][i+n-1][m][0]>maxans) maxans=f[i][i+n-1][m][0];
49: if (f[i][i+n-1][m][1]<minans) minans=f[i][i+n-1][m][1];
50: }
51: printf("%d\n%d\n",minans,maxans);
52: return 0;
53: }
54:
【题目描述】
寻找一个由n个整数组成的数列，其中任意连续p个整数之和为正，任意连续q个整数之和为负。若不存在这样的整数数列，则输出NO，否则输出其中一个数列。
【输入】
对于每个测试点将给你M组数据，要求你对于每组数据，判断是否存在这样的整数数列。
输入的第一行是一个正整数M，（1<=N<=10000）,接下来的M行对应M组数据，每行有三个正整数N、P、Q（1<=n,p,q<=10^8）。
【输出】
输出数据共N行，每行为yes或者no，如果第I组数据有解，则在第I行输出yes，否则输出no
【输入输出示例】
| 输入(sequence.in) | 输出(sequence.out) |
2
1 1 9
10 2 4 | yes
no |
【评分标准】
对于每个测试点，如果你能够在1S内通过每组数据，你将得到这个测试点的分数，否则，这个测试点你只能得0分。
【分析】
原题目是要求输出一种可能的解，如果没有解就输出-1。这样的话就要用到差分约束。
现在的话，只需要一个公式。如果有解，应满足：n<=q+p-gcd(p,q)-1。
1: #include <stdio.h>
2: #include <iostream>
3: using namespace std;
4:
5: int n,m,p,q;
6:
7: int gcd(int a,int b)
8: {
9: if (a<b) swap(a,b);
10: int t;
11: while (b!=0)
12: {
13: t=a;
14: a=b;
15: b=t%a;
16: }
17: return a;
18: }
19:
20: int main()
21: {
22: freopen("sequence.in","r",stdin);
23: freopen("sequence.out","w",stdout);
24:
25: scanf("%d",&m);
26: for (int i=0;i<m;++i)
27: {
28: scanf("%d%d%d",&n,&p,&q);
29: if (n<=p+q+gcd(p,q)-1) printf("YES\n");
30: else printf("NO\n");
31: }
32: return 0;
33: }
34:
下面是我写的查分约束。
1: #include <stdio.h>
2: #define MAXINT 1000000
3: #define maxn 1010
4:
5: struct ss
6: {
7: int x,y,dis;
8: } l[10000];
9:
10: int s[maxn];
11: int a[maxn];
12: int d[maxn];
13: int n,q,p,tot;
14:
15: int main()
16: {
17: scanf("%d%d%d",&n,&p,&q);
18: for (int i=0;i<=n;++i)
19: if (i+p>n) break;
20: else
21: {
22: l[++tot].x=i+p;
23: l[tot].y=i;
24: l[tot].dis=-1;
25: }
26: for (int i=0;i<=n;++i)
27: if (i+q>n) break;
28: else
29: {
30: l[++tot].x=i;
31: l[tot].y=i+q;
32: l[tot].dis=-1;
33: }
34: for (int i=1;i<=n;++i)
35: {
36: for (int j=1;j<=tot;++j)
37: if (d[l[j].y]>d[l[j].x]+l[j].dis)
38: d[l[j].y]=d[l[j].x]+l[j].dis;
39: for (int j=1;j<=tot;++j)
40: if (d[l[j].y]>d[l[j].x]+l[j].dis)
41: {
42: printf("-1\n");
43: return 0;
44: }
45: }
46: for (int i=0;i<=n;++i)
47: s[i]=d[i];
48: for (int i=1;i<=n;++i) printf("%d\n",s[i]-s[i-1]);
49: return 0;
50: }
51:
今天上午从东区搬东西到西区。11点都收拾完了，然后到水房泼了一个小时的水。
下午两点多的时候曹老师开始讲课。
今天的课程是两个内容：全面分析试题，动态规划。
曹老师拿他给自己的学生布置的任务做例子，大概的说了一下从一个题目的模型到完整的题目的过程。首先曹老师给了4道题目，都只是大概的描述。然后将每个条件定严谨。确定输入输出的格式。分析可以用什么算法，每种算法的时间复杂度以及可以通过的数据范围。根据算法定出数据，写出标程。曹老师说他们的学生每个人通过自己的分析，做出10个数据，然后大概100多个测试点来测试每个人写的程序。
以下是4道题目。第二题有些瓶颈，一会再发。
- 动态规划-走迷宫问题
- 空缺
- 贪心-买彩票
- 数学问题-Black and White
【题目描述】
寻找一个由n个整数组成的数列，其中任意连续p个整数之和为正，任意连续q个整数之和为负。若不存在这样的整数数列，则输出NO，否则输出其中一个数列。
【输入】
对于每个测试点将给你M组数据，要求你对于每组数据，判断是否存在这样的整数数列。
输入的第一行是一个正整数M，（1<=N<=10000）,接下来的M行对应M组数据，每行有三个正整数N、P、Q（1<=n,p,q<=10^8）。
【输出】
输出数据共N行，每行为yes或者no，如果第I组数据有解，则在第I行输出yes，否则输出no
【输入输出示例】
| 输入(sequence.in) | 输出(sequence.out) |
2
1 1 9
10 2 4 | yes
no |
【评分标准】
对于每个测试点，如果你能够在1S内通过每组数据，你将得到这个测试点的分数，否则，这个测试点你只能得0分。
【分析】
原题目是要求输出一种可能的解，如果没有解就输出-1。这样的话就要用到差分约束。
现在的话，只需要一个公式。如果有解，应满足：n<=q+p+gcd(p,q)-1。
1: #include <stdio.h>
2: #include <iostream>
3: using namespace std;
4:
5: int n,m,p,q;
6:
7: int gcd(int a,int b)
8: {
9: if (a<b) swap(a,b);
10: int t;
11: while (b!=0)
12: {
13: t=a;
14: a=b;
15: b=t%a;
16: }
17: return a;
18: }
19:
20: int main()
21: {
22: freopen("sequence.in","r",stdin);
23: freopen("sequence.out","w",stdout);
24:
25: scanf("%d",&m);
26: for (int i=0;i<m;++i)
27: {
28: scanf("%d%d%d",&n,&p,&q);
29: if (n<=p+q+gcd(p,q)-1) printf("YES\n");
30: else printf("NO\n");
31: }
32: return 0;
33: }
34:
【问题描述】
电视里面正放着“抽百万大奖，赢幸福生活”的宣传广告，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: