题解 P1717 【钓鱼】

· · 题解

这道题数据范围比较小，所以我们可以先不考虑时间复杂度（貌似关于 n 的指数算法都能过）

以下字母 T=12h （即：“单位时间”的数据范围）

引理 约翰不会掉头
证明：由于每个鱼塘能钓到的鱼与当前时间戳无关，掉头只会白白浪费时间，所以约翰不会掉头
Q.E.D.

思路 DP
考虑设计状态 dp[i][j] 表示处于第 i 个鱼塘，花费了 j 单位时间，钓到了 dp[i][j] 条鱼。
考虑转移。从 dp[i][j] 转移到 dp[k][p] ，当且仅当：

转移方程式为 dp[k][p] = \max(dp[k][p], dp[i][j]+fish(i, p- j - dist(i\ to\ k)))
其中 fish(x,y) 表示在鱼塘 x 钓 y 分钟得到的鱼数目，可以 \Theta(nT) 预处理得出。

初始化 f[0][0] 为 0 ，其余均为 -inf （注：转移时 k\in[1,n],i\in[0,n]，原理是模拟一个虚拟鱼塘 0 与鱼塘 1 处于同一位置，方便计算在鱼塘 1 钓鱼的贡献）

注意代码中的 i,j,k,p 与此处意义不相同。

时间复杂度 \Theta(n^2T^2)≈25^2*192^2≈2.3\times10^7，能过。

代码

已略去头文件 & I/O优化

//     自己选择的路，跪着也要走完。朋友们，虽然这个世界日益浮躁起来，只
// 要能够为了当时纯粹的梦想和感动坚持努力下去，不管其它人怎么样，我们也
// 能够保持自己的本色走下去。                               ——陈立杰
/*************************************
 * @problem:      P1717 钓鱼.
 * @user_id:      63720.
 * @user_name:    brealid.
 * @time:         2020-06-01.
 * @language:     C++.
 * @upload_place: luogu.
*************************************/  

const int N = 25 + 4, HT = 16 * 60 + 7;

int H, n;
int f[N], d[N], t[N];
int fish[N][HT];
int dp[N][HT];
#define dist(l, r) (t[r] - t[l])

signed main() {
    n = read<int>();
    H = read<int>() * 12;
    for (int i = 1; i <= n; i++) f[i] = read<int>();
    for (int i = 1; i <= n; i++) d[i] = read<int>();
    for (int i = 2; i <= n; i++) t[i] = t[i - 1] + read<int>();
    for (int i = 1; i <= n; i++) {
        int now = f[i];
        for (int j = 1; j <= H; j++) {
            fish[i][j] = fish[i][j - 1] + now;
            now = max(now - d[i], 0);
        }
    }
    memset(dp, 0xcf, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            for (int k = dist(j, i); k <= H; k++) {
                for (int p = k; p <= H; p++) {
                    dp[i][p] = max(dp[i][p], dp[j][k - dist(j, i)] + fish[i][p - k]);
                }
            }
        }
    }
    // for (int i = 1; i <= n; i++)
    //     for (int j = 0; j <= H; j++)
    //         printf("%-3d%c", dp[i][j], " \n"[j == H]);
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dp[i][H]);
    write(ans, 10);
    return 0;
}

// Create File Date : 2020-06-01

/*
Input
2 1
10 1
2 5
2
*/