题解 P2039 【[AHOI2009]checker】

Starria的脑残粉

2017-06-29 11:17:53

Solution

其实就是一个大暴力罢了,(看前面傅强树的提交记录是n^2的然鹅这个是on的 注意在最右边出现的红色是有效的! 注意在最右边出现的红色是有效的! 注意在最右边出现的红色是有效的! ```cpp #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; } ```