P2039 [AHOI2009]跳棋题解

long_int · 2021-09-05 11:03:52 · 题解

主要思想：动态规划

这一题可以分为两种情况讨论：没有红色块相连接和有连续两个红色块连接。首先要明确：不管是哪种情况，跳棋一定是走奇数的格子，因此最后的计数肯定要在偶数的格子上累加。

没有相连的红色块

先看一组样例：

5
0 0 0 1 0

不难发现，只需要在偶数上放跳棋，最终就能完成任务。由于题目要求游戏前尽可能放得少，而游戏开始后又只能放在红点上，所以所有的红点都给游戏开始后放。

总结：对于这种情况，第一行输出下标为偶数的点中 0 的个数，第二行输出下标为偶数的店中 1 的个数。

这一步的代码：

bool flag = false;
scanf("%lld", &n);
for (LL i = 1; i <= n; i++) {
    scanf("%lld", &q[i]);
    if (i == 1) {
        q[i] = 0; //起点的红点没有用，故赋值为 0，作为白点处理
        continue;
    }
    if (i % 2 == 0)
        num[q[i]]++;
    if (q[i] && q[i - 1])
        flag = true;
}
printf("%lld\n%lld", num[0], num[1]);

有连续至少两块红色块连接

再看一组样例：

8
0 0 0 0 0 1 1 0

此时，我们在游戏开始之前不需要放任何棋子。

具体步骤（推出状态转移方程的具体过程）：

首先在 6 和 7 的位置放棋。
然后 7 位置的棋子跳到 5 ，此时 6 被吃掉。因此，在位置 5 的地方得到一个跳棋需要放两次棋，我们记作 dp[5] = 2。
这时我们在 6 放置一个棋子，使它吃掉 5 跳到 4，记作dp[4] = 3。
此时若还想向左跳，只需要在 5 上放一个棋子。可是问题来了，5 不是红点，放不了啊！但是我们已经知道 {dp}_5 的值是 2，所以用 2 步使得 5 上面有一个棋子，再跳到 3 即可，记作dp[3] = 5。
重复以上操作，直到 2 处有一个棋子，使得需要到达终点目标棋子跳到 3 的位置。在 4 处得到一个棋子，将目标棋子调到 5 ，一直到终点为止。

通过上述步骤，不难发现一个规律：

想要在 i 的位置得到一个棋子，必须在 i+1 和 i+2 处分别放一个棋子，此时需要耗费 {dp}_{i+1} + {dp}_{i+2} 的代价。

综上所述，状态转移方程可以很轻松地得到：

{dp}_i = \min({dp}_i, {dp}_{i+1} + {dp}_{i+2})
同理，我们有：{dp}_i = \min({dp}_i, {dp}_{i-1} + {dp}_{i-2})

此时代码就很容易写出来了：

for (int i = 3; i <= n; i++)
if (q[i] && q[i - 1]) {
    for (int j = i - 2; j >= 1; j--)
        dp[j] = min(dp[j], dp[j + 1] + dp[j + 2]); //跳棋向左边跳
    for (int j = i + 1; j <= n; j++)
        dp[j] = min(dp[j], dp[j - 1] + dp[j - 2]); //跳棋向右边跳
}

完整的 AC Code：

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable : 4996)
#define maxn 1005
#define INF 1e18 //这里的INF一定要开够大小，我之前一直开到1e9，只能得60分
#define LL long long
#define bool int
#define true 1
#define false 0 //由于C语言里没有 bool 型，需要自己宏定义
LL n, q[maxn], num[2];
LL dp[maxn];
LL min(LL a, LL b) { return a < b ? a : b; }
void print(bool flag) { //输出函数
    if (!flag) {
        printf("%lld\n%lld", num[0], num[1]);
        exit(0); //直接结束程序
    }
    LL ans = 0;
    for (int i = 1; i <= n; i++)
        ans += (i % 2) ? 0 : dp[i]; //只有偶数点才计入答案
    printf("%d\n%lld", 0, ans);
}
int main() {
    bool flag = false;
    scanf("%lld", &n);
    for (LL i = 1; i <= n; i++) {
        scanf("%lld", &q[i]);
        if (i == 1) {
            q[i] = 0; //起点的红点没有用，故赋值为 0，作为白点处理
            continue;
        }
        if (i % 2 == 0)
            num[q[i]]++;
        if (q[i] && q[i - 1])
            flag = true;
    }
    for (int i = 1; i <= n; i++)
        dp[i] = q[i] ? 1 : INF;
    for (int i = 3; i <= n; i++)
        if (q[i] && q[i - 1]) {
            for (int j = i - 2; j >= 1; j--)
                dp[j] = min(dp[j], dp[j + 1] + dp[j + 2]); //跳棋向左边跳
            for (int j = i + 1; j <= n; j++)
                dp[j] = min(dp[j], dp[j - 1] + dp[j - 2]); //跳棋向右边跳
        }
    print(flag);
    return 0;
}

目前也是最优解（话说第二优似乎是抄这篇题解的）：

最后提醒：这一题会卡 long long，一定要注意！

P2039 [AHOI2009]跳棋 题解

主要思想：动态规划

P2039 [AHOI2009]跳棋题解