Description：

一个 $1$ 行 $N$ 列（ $N$ 是奇数）的棋盘上有 $K$ 个格子为红色。一个跳棋在最左端的格子上。目标是将它移动到最右边的格子，在开始移动之间可以在空位上放棋子。开始后只可以随时在红色格子上放棋子。每次可以选择一个棋子跳过与之相邻的棋子，被它跳过的棋子被吃掉。求移动开始前至少要放多少棋子，如果要使开始前放的棋子数要求尽量少，在移动过程中最少需要放多少个棋子。

Solution：

神题。

首先最后的情况是所有偶数格子上都有棋子。

如果存在两个连续的红格子，那就可以不停把一个左移，在空出来的位置再放一个，那么最开始就不用放了，这种情况下在位置 $i$ 有棋子的最小代价是 $\min((a[i]==\text{RED}?1:\text{INF}),f[i-2]+f[i-1],f[i+1]+f[i+2])$ ，正反各扫一遍，最后把所有偶数位置求和即可，这是因为在连续红格子左边都可以由右边的红格子转移，右边可以由左边转移。

如果不存在，那么直接把所有偶数格子对应颜色累加求和，白的在一开始放，红的在开始之后放。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 1010

int a[MAXN];

long long f[MAXN];

#define INF 0x3f3f3f3f3f3f3f3f

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	bool flag;

	for(int i = 2;i < n;++i)flag |= (a[i] && a[i + 1]);

	if(flag)

	{

		memset(f,0x3f,sizeof(f));

		f[1] = 0;f[0] = 0;f[n + 1] = 0;

		for(int i = 2;i <= n;++i)if(a[i])f[i] = 1;

		for(int i = 3;i <= n;++i)

			if(f[i - 2] != INF && f[i - 1] != INF)

				f[i] = min(f[i],f[i - 1] + f[i - 2]);

		for(int i = n - 2;i >= 1;--i)

			if(f[i + 1] != INF && f[i + 2] != INF)

				f[i] = min(f[i],f[i + 1] + f[i + 2]);

		long long ans = 0;

		for(int i = 1;i <= n;++i)

		{

			if((i & 1) ^ 1)ans += f[i];

		}

		cout << 0 << endl << ans << endl;

	}

	else

	{

		int ans[2] = {0,0};

		for(int i = 1;i <= n;++i)

		{

			if((i & 1) ^ 1)++ans[a[i]];

		}

		cout << ans[0] << endl << ans[1] << endl;

	}

	return 0;

}