题解：P13233 [GCJ 2015 Finals] Costly Binary Search

· · 题解

简单题。先考虑一个朴素的多项式时间复杂度做法。记 f_{i,j} 表示当前确定了要猜的数范围在 [i,j] 中，最少需要花费多少代价可以确定。转移直接枚举猜测的数 k\in[i,j]\in\mathbb{N_+} 然后将左右两段区间看作子任务递归处理即可，时间复杂度为 O(n^3)。

考虑进一步优化。注意到 a 数组的值域很小，因此考虑在这上面做手脚。考虑这个东西在不考虑 a 数组的贡献的情况下可以直接二分，期望 O(\log n) 次就可以询问出来。而又有 a_i\le 9，因此答案一定有一个 9\lceil\log n\rceil 的上界。此时考虑套路的把答案和 dp 数组的一个维度交换，设 f_{i,j} 表示当前使用了不超过 i 的代价，询问的区间右端点是 j，左端点最小可以到哪里；g_{i,j} 表示当前使用了不超过 i 的代价，询问的区间左端点是 j。该 dp 的初始条件是 f_{a_i,i}=g_{a_i,i}=i，而答案就是最小的 i 满足 g_{i,1}=n。

转移考虑从小到大枚举所有花费 i，然后再枚举选择要问的点 mid，则此时就是需要找到两个花费不超过 i-a_{mid} 的区间，可以直接利用前面处理的 f_{i-a_{mid}},g_{i-a_{mid}} 数组 O(1) 求出；另一种情况是直接从 f_{i-1},g_{i-1} 转移过来。显然这两种情况已经完全覆盖了所有可行的转移，直接模拟上述过程时间复杂度为 O(kn\log^2n)，其中 k 是 a 数组的值域大小，这里取 k=9。

但是这样转移也有一个问题：空间开不下。注意到 f_i,g_i 数组转移的过程只会利用到 f_{i-9\sim i-1},g_{i-9\sim i-1} 这 18 个位置，因此可以滚动数组，只存储最近的 i\bmod 10 的 f_i,g_i 数组即可。此时空间复杂度被优化到 O(kn)，可以通过该题。

inline void sol() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    for (int i = 0; i < 10; ++i) for (int j = 0; j <= n + 1; ++j) f[i][j] = j + 1, g[i][j] = j - 1;
    for (int i = 1; i <= n; ++i) f[s[i] - '0'][i] = g[s[i] - '0'][i] = i;
    for (int i = 0; ; ++i) {
        if (g[i % 10][1] == n) { std::cout << i << '\n'; return; }
        if (i) for (int j = 1; j <= n; ++j) f[i % 10][j] = std::min(f[i % 10][j], f[(i + 9) % 10][j]), g[i % 10][j] = std::max(g[i % 10][j], g[(i + 9) % 10][j]);
        for (int j = n - 1; j; --j) f[i % 10][j] = std::min(f[i % 10][j], f[i % 10][j + 1]);
        for (int j = 1; j < n; ++j) g[i % 10][j] = std::max(g[i % 10][j], g[i % 10][j - 1]);
        for (int j = 1; j <= n; ++j) {
            int l = f[i % 10][j - 1], r = g[i % 10][j + 1];
            chkmin(f[(i % 10 + s[j] - '0') % 10][r], l), chkmax(g[(i % 10 + s[j] - '0') % 10][l], r);
        }
    }
}