题解 P2039 【[AHOI2009]checker】

2017-06-29 11:17:53


其实就是一个大暴力罢了,(看前面傅强树的提交记录是n^2的然鹅这个是on的

注意在最右边出现的红色是有效的!

注意在最右边出现的红色是有效的!

注意在最右边出现的红色是有效的!

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000000],f[1000000],x,y;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    memset(f,10,sizeof(f));
    for (int i=1;i<=n;i++){
        cin>>a[i];
        if (a[i]&&i!=1)f[i]=1;//放一个跳棋的代价为1
    }
    for (int i=2;i<=n;i++)f[i]=min(f[i],f[i-1]+f[i-2]);
    for (int i=n;i>=1;i--)f[i]=min(f[i],f[i+1]+f[i+2]);//即i这个位置的跳棋可以由相邻的连续两个跳棋转移
    for (int i=1;i<=n;i++)
        if (i%2==0){
                if (f[i]>1e15)x++;//这个位置不能由单纯的在红色位置放跳棋转移
                    else y+=f[i];
            }
    cout<<x<<endl<<y<<endl; 
}