2 条题解
-
0
何老师 (root) LV 0 MOD @ 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有关的全部都移项移出来,就可以放到单调队列里 -
02020-08-23 11:14:28@
显然是个背包,发现可以单调队列优化,需要注意的是限制条件,如果大了的话要提前更新。
- 1