题目链接： https://vjudge.net/problem/LightOJ-1106
题意
给出n个湖，John最开始在第一个湖并且有h个小时的时间，每个湖初始可以钓到f只鱼，每单位时间可以钓到的鱼减少d只（单位时间为5分钟，不足d只时减少为0），从第i个湖到第i+1个湖需要t[i]单位时间。求最多能够钓到鱼的数量和在每个湖花费的时间。
数据
输入第一行表示数据组数 T，T <= 100
对于每组测试数据，第一行为n和h，2 <= n <= 25，1 <= h <= 16
接下来一行为n个整数f[i]，0 <= f[i] <= 1000
接下来一行为n个整数d[i]，0 <= d[i] <= 1000
接下来一行为n-1个整数t[i]，0 < t[i] < 192
输入
3
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
输出
Case 1:
45, 5
Number of fish expected: 31
Case 2:
240, 0, 0, 0
Number of fish expected: 480
Case 3:
115, 10, 50, 35
Number of fish expected: 724
解题方法： 1， 贪心，堆优化（由于数据比较小，可以直接暴力）
首先我们可以枚举要走过湖泊数X，然后算出从1到X的时间。那么在这个前提下，我们可以认为fisher可以从一个湖泊“瞬间转移”到另一个湖泊，即在任意一个时刻可以从1到X中任选一个钓鱼。
此时，走路的时间确定了，钓鱼的次数就确定了（每次5分钟），然后每次都选取f[i]最大的钓，这种贪心的思想最终能够得到一个钓鱼序列。
你可能会跟我一样有一个疑问：因为就算是在这种情况下求出的钓鱼序列 为 1 ，5，6， 2， 3， 2，7 ，你可能会认为到了湖泊6之后再回到湖泊2可能要再花时间而且题目也不允许，但是这只是钓鱼序列，我们可以用 1 2 2 3 5 6 7 来实现这种钓鱼序列。
复杂度 O(n * n * h)
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define mep(i, a, b) for(int i = a; i < b; i++)
#define uep(i, a, b) for(int i = a; i >= b; i--)
#define cls(a, b) memset(a, b, sizeof(a))
int f[30], d[30], t[30];
int T, n, h, ks;
int maxtime, ans_time[30], fishtime;
int main(){
ks = 0;
scanf("%d", &T);
while(T--){
scanf("%d%d", &n, &h);
rep(i, 1, n) scanf("%d", &f[i]);
rep(i, 1, n) scanf("%d", &d[i]);
mep(i, 1, n) scanf("%d", &t[i]);
maxtime = 0;
cls(ans_time, 0);
rep(i, 1, n){ //枚举一下走过的湖泊数
int tmpsum = 0, sum = 0;
mep(j, 1, i){
sum += t[j]*5;
}
fishtime = (h * 60 - sum) / 5; //剩下的捕鱼时间，这里面可以瞬间转移
int curf[30], cur_ans_time[30];
cls(cur_ans_time, 0);
rep(j, 1, i) curf[j] = f[j];
rep(j, 1, fishtime){
int mxpos = 1;
rep(k, 1, i){ //可以堆优化
if(curf[k] > curf[mxpos]){
mxpos = k;
}
}
tmpsum += curf[mxpos];
curf[mxpos] -= d[mxpos];
if(curf[mxpos] < 0){
curf[mxpos] = 0;
}
cur_ans_time[mxpos] += 5;
}
if(tmpsum > maxtime){
rep(i, 1, n){
ans_time[i] = cur_ans_time[i];
}
maxtime = tmpsum;
}
}
printf("Case %d:\n", ++ks);
printf("%d", ans_time[1]);
rep(i, 2, n){
printf(", %d", ans_time[i]);
}
printf("\n");
printf("Number of fish expected: %d\n", maxtime);
}
return 0;
}
解题方法2： 除了贪心，还可以DP。。是wannafly菊苣的解法，设dp[i][j]表示i开始剩余时间是j的最大捕鱼量
每次枚举第i个湖上的钓鱼时间k，有dp[i][j] = max(dp[i - 1][j - k] + cost[i][k]), cost表示第i个湖捕k时间鱼的收获
贴一下大神给出的代码，来研究一下：
京公网安备 11010502036488号