NC19884. [AHOI2009]CHECKER
描述
输入描述
第一行一个正奇数N
第二行有N个整数，如果第i个整数是非功过，说明第i个格子是红棋，否则为白棋，数字间用空格分开.
输出描述
两个数字分别代表第一问和第二问的结果.
示例1
输入:
5 0 0 0 1 0
输出:
1 1
说明:
在游戏开始前，可以在第二个格子上放上一个棋子，游戏开始后可用最左边的棋子吃掉它，从而移动到第三格。然后由于第四格是个红色的格子，在游戏中可以在那放一个棋子，然后用已经移动第三格的棋子把它吃掉，从而达到终点。
C++11(clang++ 3.9) 解法, 执行用时: 12ms, 内存消耗: 1272K, 提交时间: 2019-12-30 19:50:42
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,i,ans,f[100010],a[100010],flag,c[2];
int main(){
scanf("%lld",&n);
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
for(i=3;i<=n;i++)if(a[i]&&a[i-1])flag=1;
if(!flag){
for(i=2;i<=n;i+=2)c[a[i]]++;
printf("%lld\n%lld",c[0],c[1]);
return 0;
}
memset(f,44,sizeof(f));
for(i=2;i<=n;i++)if(a[i])f[i]=1;
for(i=3;i<=n;i++)f[i]=min(f[i],f[i-1]+f[i-2]);
for(i=n;i>=2;i--)f[i]=min(f[i],f[i+1]+f[i+2]);
for(i=2;i<=n;i+=2)ans+=f[i];
printf("0\n%lld",ans);
}