很好的一道思维题，代码本身难度不高，但是需要认真思考思考。

先分析一下题意： 我们需要用题目给出的方式，选择一个方案构造出一个所有偶数位置都有一个马的状态，满足在游戏开始前放的马（不难看出，这其实可以等效替代为 “在白色格子中放的马” ）尽可能少，如果有多种方式，再选择在游戏开始后放的马（同理，可以等效替代为 “在黑色格子中放的马”）最少的方案，你只需要输出开始前和开始后放马的数量。

刚看到这道题时，似乎没什么思路。不如看看样例：（以下红马代表开始前放置，绿马代表开始后放置）

我们可以得出：当有两个相邻黑格子的时候，一定有方案可以让我们在开始前无需放马。

那么我们可以分两种情况：

1.没有两个相邻的黑格子：

• 很简单，只需要看偶数位的格子，如果是白色，那么第一位答案+1，否则第二位答案+1（开始前/后放的马等效替代为在白/黑格子放的马）

2.有两个相邻的黑格子：

• 第一位答案就是0，接下来求第二位答案。

• 鉴于一个白格子上的马一定是从向前第二个位置或向后第二个位置跳过来的，而这样需要满足向前第一个位置或向前第一个位置有马，可以考虑dp。

• 状态设置：f[i]表示令第i位有马需要放i只马。

• 

• 初始状态：如果这个位置是黑格子，那么设为1，否则设为无限大（注意不要让其*2后就爆了）。

• 最终的第二位答案就是所有偶数位的f的和啦。

但是注意，有坑！，第一号格子是不能放额外的马的，所以在判断是否有黑格子的时候，不能算上第一号格子，并且转移的时候第一号格子也不能参与。

代码很简单，就不放出来了。

转移只需要一层for，整体时间复杂度是O(n)，过题绰绰有余。