分析
对于两个问题,我们可以分开讨论。我们发现如果有两个相邻的红色的砖块(不包括节点 ),那么在开始之后就可以使棋子到达任意一个地方,那么我们就根据是否有两个相邻的红色砖块来讨论。
无相邻的情况,我们可以发现,直接把棋子放在偶数位置是最优的。那么第一问的答案就是偶数位置 的个数,而第二问就是偶数位置 的个数。
有相邻的情况,我们可以发现第一问的答案为 ,而第二问,我们考虑递推, 表示在这个节点放一个棋子总共需要安放的棋子数,那么转移和斐波那契数列是一样的 。当然正反都要来一次,我们从任意两个相邻的红色砖块开始都有这样的转移,那么总的复杂度就为 。
细节,开 ,而且要注意节点 ,是不记做红色的。
代码
#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; }