题目分析
动态规划。
\(\bullet\) 设计状态。
思考：我从哪里来？从上一个湖过来。
我到哪里去？到下一个湖去 \(or\) 继续在这个湖钓鱼。
设 \(dp[pos][tim]\) 为前 \(pos\) 个湖花费了 \(tim\) 分钟所能钓的最大的鱼数量。
\(\bullet\) 转移状态。（为了方便计算，我们将题目中的数据全部除以 \(5\)，结果不变。）
\(c\) 表示已经在当前第 \(pos\) 个湖停留钓鱼了 \(c\) 分钟。
\(fish[i]\) 表示第 \(i\) 个湖最多钓的鱼。
\(t\) \(d\) 含义同原题题面的解释。
转移方程：\(dp[pos][tim]=max(dp[pos-1][tim-t[pos-1]-c]+\sum_{i=0}^{c-1}(fish[pos]-i*d[pos]))\)
为了方便计算，我们将这个式子用等差数列求和公式展开后半部分。
即：\(dp[pos][tim]=max(dp[pos-1][tim-t[pos-1]-c]+c*(fish[pos]+fish[pos]-(c-1)*d[pos])/2)\)
解释含义：\(tim-t[pos-1]-c\) 表式上一个湖结束钓鱼时已花费的时间。（当前时间-从上个湖到当前湖花费的时间-当前湖已经花费的时间。）
代码
依题意枚举 \(pos\) \(tim\) \(c\)。
注意：
\(\bullet\) 注意含有减法下标的越界情况。
\(\bullet\) 若 \(dp[pos-1][tim-t[pos-1]-c]\) 还没赋值，continue。
\(\bullet\) 若当前能获得的鱼 \(<=0\)，continue。
代码实现：
#include <bits/stdc++.h>
#define int long long
const int N = 10005;
using namespace std;
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-'){
w = -1;
}
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
int n,h,fish[N],d[N],t[N];
int dp[105][N];
signed main(){
n = read(),h = read();
h *= 12;
for (int i = 1;i <= n;i++){
fish[i] = read();
}
for (int i = 1;i <= n;i++){
d[i] = read();
}
for (int i = 1;i <= n - 1;i++){
t[i] = read();
}
int ans = -1;
memset(dp,-1,sizeof(dp));
dp[0][0] = 0;
for (int pos = 1;pos <= n;pos++){
for (int tim = 0;tim <= h;tim++){
for (int c = 0;tim - t[pos - 1] - c >= 0;c++){
if (dp[pos - 1][tim - t[pos - 1] - c] != -1 && fish[pos] - (c - 1) * d[pos] > 0){
dp[pos][tim] = max(dp[pos][tim],dp[pos - 1][tim - t[pos - 1] - c] + c * (fish[pos] + fish[pos] - (c - 1) * d[pos]) / 2);
ans = max(ans,dp[pos][tim]);
}
}
}
}
printf("%lld",ans);
return 0;
}