题解：AT_abc192_f [ABC192F] Potion

Louis_lxy · 2024-09-08 11:24:01 · 题解

一种与众不同的 dp。

考虑暴力 dp，令 f(i,j,k,l) 表示前 l 个数中取 i 个数的和在模 j 下余 k 的最大的和，然后暴力转移，此时空间 O(n^4)，时间 O(n^5)，然后发现空间可以滚掉，然后空间变成了 O(n^3)，然后发现时间好像不好优化。但是只要加上剪枝就可以通过这题。

剪枝一：显然只有存在 f(i-1,j,(k-a_l)\bmod j,l-1) 才有可能转移。

剪枝二：容易发现 f 数组在前三维相同的情况下，数据单调不减，因此只需要在更新 f 的时候判断是否能更新，如果不能更新，后面的也一定不能更新。

接着证明一下 f 数组在前三维相同的情况下，数据单调不减。容易发现，f(i,j,k,l) 要么是 f(i,j,k,l-1)，要么包含 a_l，因此一定不小于 f(i,j,k,l-1)。

也可以用线段树优化，但是这样是稳定 O(n^4\log n)，无法通过此题。

AC 记录：https://www.luogu.com.cn/record/176263173

注：希望有神犇能证明其复杂度正确，或者给出 hack，如果有神犇会，可以发在评论区。