题解

2 条题解

  • 0
    @ 2023-03-23 09:33:07

    题解:
    这题需要一种奇怪的思想:我们知道一顿饲料如果买了,必将一直影响到最后,于是我们将后来的消费就算到状态里去
    于是可以定义f[i][j]表示前i个买j吨一直到终点的花费.然后发现可以消维.
    保留f[j]即可

    定义d[i]为i到终点的距离.
    f[j]=min(f[k]+j^2*d[i]-k^2*d[i]+j*F[i])
    把k有关的全部都移项移出来,就可以放到单调队列里

  • 0
    @ 2020-08-23 11:14:28

    显然是个背包,发现可以单调队列优化,需要注意的是限制条件,如果大了的话要提前更新。

  • 1

信息

ID
2089
难度
9
分类
动态规划 | 背包 点击显示
标签
递交数
1
已通过
1
通过率
100%
被复制
1
上传者