[dp trick] Exact Payment

_Cheems · 2023-11-09 07:53:00 · 个人记录

小清新题一道。

思路

题目是要求每一位可能取到的最大值，考虑每位分别计算。

然后可以背包。我们想把 第 i 位最大值 转化为 数的最大值。结合上面，不难想到状态：f_p 表示在模 10^i 意义下，p 是否存在。那么第 i 位答案就是 \max p/10^{i-1},f_p=true。

考虑优化这个过程。好像没必要存第 i 位相等的状态太多次。刚好有个 trick：

• 对于状态 A<B<C,C-A\le 10^{i-1}。则 B 对答案的所有可能贡献都会被 A,C 取到。

证明参自 Lgx_Q：考虑后面取的和为 v，则 (C+v)-(A+v) \le 10^{i-1}，这等价于模后两数的最高位差值不超过 1。故结论成立。

那么每个时刻的合法状态数不超过 10，只需在转移后及时去除冗余状态即可。

那每一位的求解就是 O(10n) 的。总体复杂度 O(n\log_{10} V) 接 10 的常数。