bzoj 3692: 愚蠢的算法 dp

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=3692


居然是NOI2018的80分的原题!

$f[i][j]$ 表示用了 $i$ 个数,最大的数为 $j$ 。

这样转移的时候是 $n^3$ 的,再维护一下 $i-1$ 的前缀和,这样转移的时候就是 $n^2$ 的了。

 

张贴在DP

发表评论