题面

https://www.luogu.com.cn/problem/P1717

题解

以五分钟为一个单位，设状态方程：$g[i][j]$ 表示第 $i$ 个时间单位到达 $j$ 农场钓到的鱼。

$$
g[i][j] = \max_{0 \leq k \leq i - t[j]} \{g[i - t[j] - k][j-1] + \sum_{p = 0}^{k-1} \max (0, f[j] - p \times d[j])\}
$$

注意：这里的 $t[i]$ 和原题中不一样，是偏移过一位的。

值得注意的是

$$
f[j] - p \times d[j]
$$

需要保证大于零。

以及我们还需要保证状态是可达的才行。所以代码中要 memset -1.

代码

#include <iostream>
#include <cstring>

using namespace std;

const int maxn = 30;
const int maxt = 1e5+5;

int f[maxn], d[maxn], t[maxn], g[maxt][maxn];

int calc(int i, int j, int k) {
    int ret = g[i - t[j] - k][j - 1];
    if (ret == -1) return ret;
    for (int i = 0; i < k; i ++)
        ret += max(0, f[j] - i * d[j]);
    return ret;
}

int main() {
    int n, h; cin >> n >> h;
    h *= 12;
    for (int i = 1; i <= n; i ++) cin >> f[i];
    for (int i = 1; i <= n; i ++) cin >> d[i];
    for (int i = 2; i <= n; i ++) cin >> t[i];
    memset(g, -1, sizeof(g));
    g[0][0] = 0;
    for (int i = 1; i <= h; i ++)
        for (int j = 1; j <= n; j ++)
            for (int k = 0; k <= i - t[j]; k ++)
                g[i][j] = max(g[i][j], calc(i, j, k));
    int ans = 0;
    for (int i = 1; i <= n; i ++)
        ans = max(ans, g[h][i]);
    cout << ans << endl;
    return 0;
}