题解：CF2171H Shiori Miyagi and Maximum Array Score

· · 题解

独立做出来一道 *2400，开心。

考虑朴素 DP 方程：设 f_{i,j} 表示令 a_i=j 时的最大答案，那么显然有转移方程：

f_{i,j}=\max_{k=1}^{j-1}f_{i-1,k}+v(i,j)

最大值可以每次循环完 j 之后递推一遍。这样是 O(nm \log m) 的。

这个里面有很多无用的状态。考虑优化。

其中这个 j 要么是 i \mid j，要么是 i \nmid j（废话）。如果 i \mid j，那么会更新答案，显然是有用状态；对于 i \nmid j，假设在 i-1 中有用的 j 里面比当前的 j 小的里面最大的那个是 k，那么你把 j 换成 k+1 一定不劣，因此只保留 k+1 这个状态就行了。

但是这样过不去。为什么？我们每一次输出有用的状态看看，发现总共有用的状态达到了大约 O(nm) 个，而这是不可接受的！

怎么优化？如果对于两个状态 j 和 k，如果 j<k 且 f_{i,j}>f_{i,k}，那么 k 就很劣，可以删掉。加了这个优化之后，总状态数来到了 O(n \ln n)。

那么总时间复杂度就是 O(n \ln n \log n)，可以通过！注意需要滚动数组，以及数组使用 vector，用多少开多少。

AC Record。