思路:DP
首先自己观察一波,发现如果有相邻两个格子都是红色的话,那么显然可以在任意位置都存在一个跳棋。可以让两个位置反复互相跳就好了。这样子第一问的答案显然就是0,否则的话第一问的答案就是偶数位置上0的个数。
如果没有相邻的两个位置都是红格子,我们还可以得出第二问的答案就是偶数位置上红格子的数目。
现在有两个红格子相邻,设f[i]表示在i这个位置要出现一个棋子的最小加入的跳棋数目,显然可以暴力dp。那么最终的答案就是所有偶数位置上的f的和。
代码如下:
#include<bits/stdc++.h> using namespace std; #define ll long long #define MAX 1010 inline int read() { int x=0;bool t=false;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=true,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return t?-x:x; } int n,a[MAX];ll f[MAX];bool fl; int main() { n=read(); for(int i=1;i<=n;++i)a[i]=read(); for(int i=3;i<=n;++i) if(a[i]&&a[i-1])fl=true; if(!fl) { int s[2]={0,0}; for(int i=2;i<=n;i+=2)s[a[i]]+=1; printf("%d\n%d\n",s[0],s[1]); return 0; } puts("0");memset(f,63,sizeof(f)); for(int i=2;i<=n;++i)if(a[i])f[i]=1; for(int i=2;i<n;++i) if(a[i]&&a[i+1]) { for(int j=i-1;j>1;--j)f[j]=min(f[j],f[j+1]+f[j+2]); for(int j=i+2;j<=n;++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("%lld\n",ans); return 0; }