P9821 [ICPC2020 Shanghai R] Sum of Log 官方题解

· · 题解

以下内容转载自官方题解：

考虑数位 DP。设 dp[i][\mathrm{state}] 表示当前考虑到第 i 位，\mathrm{state} 包含的状态有：当前 x 是否卡住 X 的上界、当前 y 是否卡住 Y 的上界、当前数字是否为 0，在这基础上的答案。然后从高到低枚举 i，再枚举 x,y 在第 i 位上的状态，可以维护出后继状态，然后转移即可。