「寄予后人」RE #1 #2
  • 板块P1717 钓鱼
  • 楼主LyccriusRecoil
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/2/2 13:12
  • 上次更新2023/10/24 02:04:33
查看原帖
「寄予后人」RE #1 #2
278046
LyccriusRecoil楼主2023/2/2 13:12
if (k <= f[i] / d[i] + 1) 

注意 d[i]d[i] 作为除数可能为 00

if (d[i] && k <= f[i] / d[i] + 1)

不可以将 d[i]=0d[i] = 0 的情况排除。

std::fill(dp[0], dp[0] + (maxN + 10) * (maxH * 12 + 10), -inf);
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        //printf("i = %d\n", i);
        for (int j = 1; j <= H; j++) {
            //printf("j = %d\n", j);
            for (int k = 0; k <= j - t[i - 1]; k++) {
                //printf("k = %d\n", k);
                if ((k - 1) * d[i] < f[i]) {
                    dp[i][j] = std::max(dp[i][j], dp[i - 1][j - t[i - 1] - k] + k * f[i] - k * (k - 1) / 2 * d[i]);
                    //printf("dp[%d][%d] = %d\n", i, j, dp[i][j]);
                    ans = std::max(ans, dp[i][j]);
                }
            }
        }
    }
2023/2/2 13:12
加载中...