分析

对于两个问题,我们可以分开讨论。我们发现如果有两个相邻的红色的砖块(不包括节点 ),那么在开始之后就可以使棋子到达任意一个地方,那么我们就根据是否有两个相邻的红色砖块来讨论。

  • 无相邻的情况,我们可以发现,直接把棋子放在偶数位置是最优的。那么第一问的答案就是偶数位置 的个数,而第二问就是偶数位置 的个数。

  • 有相邻的情况,我们可以发现第一问的答案为 ,而第二问,我们考虑递推, 表示在这个节点放一个棋子总共需要安放的棋子数,那么转移和斐波那契数列是一样的 。当然正反都要来一次,我们从任意两个相邻的红色砖块开始都有这样的转移,那么总的复杂度就为

  • 细节,开 ,而且要注意节点 ,是不记做红色的。

代码

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const int N = 1e3 + 100;
const ll inf = 1e18;
int n,a[N],c[2];ll f[N],flag = 0;
int main() {
    n = read();
    for(int i = 1;i <= n;i++) a[i] = read();
    for(int i = 2;i <= n;i++) if(a[i] + a[i + 1] == 2) flag = 1;
    if(flag == 0) {
        for(int i = 2;i <= n;i += 2) c[a[i]]++;
        printf("%d\n%d\n",c[0],c[1]);  
    }
    else {
        f[1] = inf;
        for(int i = 2;i <= n;i++) f[i] = (a[i] == 1) ? 1 : inf;
        for(int i = 2;i <= n;i++) {
            if(a[i] + a[i + 1] == 2) {
                for(int j = i + 2;j <= n;j++) f[j] = min(f[j],f[j - 1] + f[j - 2]);
                for(int j = i - 1;j >= 1;j--) f[j] = min(f[j],f[j + 1] + f[j + 2]);
            }
        }
        ll ans = 0;
        for(int i = 2;i <= n;i += 2) ans += f[i];
        printf("0\n%lld\n",ans);
    }
    return 0;
}