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);
        }
    }
}

隐藏／恢复文章

随机文章