1.题意：有n个湖可以钓鱼，你有h个小时，假设湖按照直线排列，只有一条路可以走，John从湖1开始走，它可以从一个湖到另一个湖，间隔是5分钟，路上需要时间为ti,在每个湖前5分钟可以钓到fi条鱼， 接着的每隔5分钟减少di条鱼，求在规定时间内可以钓到多少条鱼？
2 1 10 1 2 5 2 4 4 10 15 20 17 0 3 4 3 1 2 3 4 4 10 15 50 30 0 3 4 3 1 2 3 0
样例解析：2代表有2个湖
1代表有1个小时
10 1分别代表第一个和第二个湖前五分钟钓到的鱼数；
2 5分别代表接下来每五分钟减少的数目
2代表从第一个湖到第二个湖的时间
2.解题思路：从第一个湖开始走，判断在相同时间内在第i个湖钓的多还是在第i+1个湖钓的多，核心代码 dp[i+1][j+k+ti[i+1]]=max(dp[i][j]+sum,dp[i+1][j+k+ti[i+1]]);
注意输出及idx=1；
3.代码：
#include<stdio.h>
#include<algorithm>
#include<String.h>
int dp[30][400];
int fi[30][400];
int di[30];
int ti[30];
int max(int a,int b)
{
if(a>=b)
return a;
else return b;
}
void slove(int n,int h)
{
dp[0][0]=0;
for(int i=0; i<n; i++)
{
for(int j=0; j<=h; j++)
{
int sum=0;
for(int k=0; k<=h&&dp[i][j]!=-1; k++)
{
if(j+k+ti[i+1]>h)
break;
dp[i+1][j+k+ti[i+1]]=max(dp[i][j]+sum,dp[i+1][j+k+ti[i+1]]);
if(fi[i+1][k+1]>0)
sum+=fi[i+1][k+1];
}
}
}
//printf("Number of fish expected: %d\n",dp[n][h]);
int Max=0,idx=1;
for(int i=0; i<=n; i++)
{
if(Max<dp[i][h])
{
Max=dp[i][h];
idx=i;
}
}
int maxx=Max;
int jj;
for(int i=idx;i>=2;i--)
{
int sum=0;
for(int j=0;j<=h;j++)
{
if(Max==sum+dp[i-1][h-j-ti[i]])
{
fi[i][0]=j;
jj=j;
break;
}
sum+=fi[i][j+1];
}
h=h-jj-ti[i];
Max-=sum;
}
fi[1][0]=h;
int i;
for(i=1;i<n;i++)
printf("%d, ",fi[i][0]*5);
printf("%d\n",fi[i][0]*5);
printf("Number of fish expected: %d\n\n",maxx);
}
int main()
{
int n,hi;
while(scanf("%d",&n)!=EOF)
{
memset(dp,-1,sizeof(dp));
memset(fi,0,sizeof(fi));
if(n==0)
break;
scanf("%d",&hi);
int h=hi*12;
for(int i=1; i<=n; i++)
scanf("%d",&fi[i][1]);
for(int i=1; i<=n; i++)
scanf("%d",&di[i]);
for(int i=2; i<=n; i++)
scanf("%d",&ti[i]);
ti[1]=0;
for(int i=1; i<=n; i++)
{
for(int j=2; j<=h; j++)
{
if(fi[i][j-1]-di[i]<=0)
break;
fi[i][j]=fi[i][j-1]-di[i];
}
}
slove(n,h);
}
}