题解 P2039 【[AHOI2009]跳棋】

· · 题解

解题思路

逻辑非常乱的一题。

首先假设如果没有红色格子，为了使棋数最小化，一定是将棋子放在偶数的位置。

如果有了红色格子的存在，情况又会多一些。

考虑没有两个红色格子是相邻的，仍然是把棋子下到偶数位置上的，只不过白色格子是游戏前放的，红色格子是游戏中放的，这些可以直接计数。

然而一旦有两个红色格子是相邻的，就没有必要再游戏前放棋子了。因为可以直接把棋下在这两个相邻的红色格子上，然后交替着跳，被跳过的棋子可以按照之前的步骤补回来。也就意味着每个位置都是可以被跳到的。

这种情况下，第一问的答案无疑就是 0 了，第二问的答案还需要利用 dp 求出。

设 f_i 表示要在第 i 个位置上放棋，最少需要在红色格子上放多少棋。

初始化：白色格子的 f_i = \infty，红色格子的 f_i = 1。

转移的话，按照上面说的，我们可以交替着跳到那个格子。要跳到 i，可以现想办法跳到 i + 1 和 i + 2，然后 i + 2 就可以跳到 i 了，不难发现转移式：f_i = \min\{f_i,\ f_{i+1} + f_{i+2}\}。同理可以从左边跳过来：f_i = \min\{f_i,\ f_{i-1} + f_{i-2}\}。

看起来两个式子是交替更新的，实际上，只要有相邻的红色格子，O(n) 往两边分别更新就行了，整体复杂度 O(n^2)。

最后，不要忘了偶数位置上放棋是最优的，所以 ans = \sum\limits_{i \mod 2 = 0}f_i。

代码实现

注意最后才能移走起点的棋子，所以起点的红色应该看作白色。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>

const int maxN = 1005;

int n, cnt[2], a[maxN];
long long ans, f[maxN];
bool flag = true;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); }
    a[1] = 0; // 初始位置的红色是没有用的.
    for (int i = 1; i <= n; i++) {
        if (i % 2 == 0) { cnt[a[i]]++; } // 偶数位置记录红色白色的数量.
        if (a[i - 1] + a[i] == 2) { flag = false; } // 红色相邻.
    }
    if (flag) { printf("%d\n%d\n", cnt[0], cnt[1]); } else {
        for (int i = 1; i <= n; i++) { f[i] = a[i] ? 1 : 1e18; } // 初始化 dp.
        for (int i = 1; i <= n; i++) {
            if (a[i - 1] + a[i] == 2) {
                for (int j = i - 2; j >= 1; j--) { f[j] = std::min(f[j], f[j + 1] + f[j + 2]); } // 往左跳.
                for (int j = i + 1; j <= n; j++) { f[j] = std::min(f[j], f[j - 1] + f[j - 2]); } // 往右跳.
            }
        }
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 0) { ans += f[i]; } // 偶数位置统计答案.
        }
        printf("%d\n%lld\n", 0, ans);
    }
    return 0;
}