Rockdu's Blog

题目描述

在一个1行N列（N是奇数）的棋盘上，有K个格子是红色的。这种情况下，你有一个跳棋在最左端的格子上。你的目标是将它移动到最右边的格子，在开始移动之间，你可以在棋盘的任意空位上放棋子。在游戏开始后 你只可以随时在一个红色格子上放棋子。棋子的移动规则是：每次只可以选择一个棋子，跳过与之相邻的棋子走到后面的空格上，被它跳过的棋子被吃掉，即从棋盘上移走，如相邻棋子的另一侧有棋子，则不能跳。

请回答以下两个问题：

1：移动开始前至少要放多少棋子才能完成任务。

2：如果要使开始前放的棋子数要求尽量少，那么在移动过程中最少需要放多少个棋子才能完成任务。

关于规则的补充说明：

1：只能往空位上放棋子，不管是移动开始前还是移动过程中。

2：移动前棋盘最左端的那个原始棋子绝对不能被吃掉.

输入输出格式

输入格式：

第一行一个正奇数N.

第二行有N个整数,如果第i个整数是1,说明第i个格子是红棋,否则为白棋.

数字间用空格分开

输出格式：

两个数字分别代表第一问和第二问的结果.

输入输出样例

5
0 0 0 1 0

1
1

说明

在游戏开始前，可以在第二个格子上放上一个棋子，游戏开始后可用最左边的棋子吃掉它，从而移动到第三格。然后由于第四格是个红色的格子，在游戏中可以在那放一个棋子，然后用已经移动第三格的棋子把它吃掉，从而达到终点。

100%的数据中，N< = 1000,输出中的数字不超过10^ 15

30%的数据中,N< = 20

Source: [Ahoi2009] checker

一道很细节的细节题，刚开始一看可能会以为这是个输入输出题，但是我们考虑一个白格子上的棋子实际上可以由连续的红格子刷出来。那么只要有连续的红格子就一个棋子也不用多花。所以我们对每一个白格子求最少需要在连续的红格子上刷多少个棋子才能推进到这里。然后另一个细节来了：棋子不仅可以正着跳，还可以倒着跳，所以我们正反递推一下取一个min就行了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e5 + 5;
int n, mp[maxn];
LL f[maxn], b[maxn], a1, a2;

int main() {
    scanf("%d", &n);
    for(register int i = 1; i <= n; ++i)
        scanf("%d", &mp[i]);
    memset(f, 0x3f, sizeof(f));
    memset(b, 0x3f, sizeof(b));
    if(mp[2]) f[2] = 1;
    for(register int i = 3; i <= n; ++i) {
         if(mp[i]) f[i] = 1;
         if(f[i - 2] == inf || f[i - 1] == inf) continue;
         f[i] = min(f[i - 1] + f[i - 2], f[i]);
    }
    if(mp[n]) b[n] = 1;
    if(mp[n - 1]) b[n - 1] = 1;
    for(register int i = n - 2; i >= 1; --i) {
         if(mp[i]) b[i] = 1;
         if(b[i + 2] == inf || b[i + 1] == inf) continue;
         b[i] = min(b[i + 1] + b[i + 2], b[i]);
    }
    for(register int i = 1; i <= n; ++i) {
        if(f[i] == inf) f[i] = b[i];
        else if(b[i] != inf) 
            f[i] = min(b[i], f[i]);
    }
    for(register int i = 2; i <= n; i += 2) {
        if(f[i] != inf) a2 += f[i];
        else ++a1;
    }
    printf("%lld\n%lld", a1, a2);
    return 0;
}