题目大意：john现有h个小时的空闲时间，他打算去钓鱼。john钓鱼的地方共有n个湖，所有的湖沿着一条单向路顺序排列（john每在一个湖钓完鱼后，他只能走到下一个湖继续钓），john必须从1号湖开始钓起，但是他可以在任何一个湖结束他此次钓鱼的行程。输入给出john在每个湖中每5分钟钓的鱼数（此题中以5分钟作为单位时间），随时间的增长而线性递减。而每个湖中头5分钟可以钓到的鱼数以及每个湖中相邻5分钟钓鱼数的减少量，John从任意一个湖走到它下一个湖的时间。

解题思路：1）设fish[i][j]表示到了第i个池塘用了j*5分钟所钓到的雨的数目
               2）转移：fish[i][j]=Max{fish[i-1][j-k-t[i]],fish[i][j]+sum}
                     sum是呆着这个池塘经过k*5分钟所钓到的鱼的数目~sum=f[i]*(k+1)-(k+1)*k/2*d[i]

代码：
 1#include <iostream>
 2#include <cstdio>
 3#include <cstring>
 4#include <cstring>
 5#include <cmath>
 6#include <algorithm>
 7
 8using namespace std;
 9
10int f[30],d[30],t[30],path[30];
11int fish[30][400];
12int n,h,maxx,k;
13
14void init()
15{
16    memset(path, 0, sizeof(path));
17    memset(fish,-1,sizeof(fish));
18}
19
20void find_Path(int i, int time)
21{
22    if(i==0) return;
23    int summ=0;
24    for(int k=0; k<=12*h; ++k)
25    {
26        if(fish[i-1][time-k-t[i-1]]+summ==fish[i][time])
27        {
28            path[i]=k*5;
29            return find_Path(i-1,time-k-t[i-1]);
30        }
31        if (f[i]-k*d[i]>0)
32            summ=f[i]*(k+1)-(k+1)*k/2*d[i];
33    }
34}
35
36void get_DP()
37{
38    fish[0][0]=0;
39    for(int i=0; i<=n-1; ++i)
40        for(int j=0; j<=12*h; ++j)
41        {
42            int summ=0;
43            for(int k=0; k<=12*h && fish[i][j]!=-1; ++k)
44            {
45                if(j+k+t[i]<=12*h)
46                    fish[i+1][j+k+t[i]]=max(fish[i+1][j+k+t[i]],fish[i][j]+summ);
47                else
48                    break;
49                if (f[i+1]-k*d[i+1]>0)
50                   summ=f[i+1]*(k+1)-(k+1)*k/2*d[i+1];
51            }
52        }
53        maxx=0;
54        k=1;
55        for(int i = 1; i <= n; ++i)
56            if(maxx<fish[i][12*h])
57            {
58                maxx=fish[i][12*h];
59                k=i;
60            }
61}
62
63int main()
64{
65    while (~scanf("%d",&n))
66    {
67        if (n==0) break;
68        scanf("%d",&h);
69        for (int i=1; i<=n; i++) scanf("%d",&f[i]);
70        for (int i=1; i<=n; i++) scanf("%d",&d[i]);
71        for (int i=1; i<=n-1; i++) scanf("%d",&t[i]);
72        init();
73        get_DP();
74        find_Path(k, 12*h);
75        for(int i = 1; i <= n-1; ++i)
76            printf("%d, ",path[i]);
77        printf("%d\n",path[n]);
78        printf("Number of fish expected: %d\n", fish[k][12*h]);
79        printf("\n");
80    }
81    return 0;
82}
83