The Water Bowls [POJ3185] [开关问题]

题意

一串长度为20的0,1数列,每次翻转i,会影响i-1,i+1,也被翻转,最少翻转成0的步骤数是多少?

Sample Input

0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0

Sample Output

3

分析

这一道开关问题和POJ3276很类似,但是那个是有固定长度的,我们可以看做是一个点向后的一个区间进行翻转,就不会对前面产生影响.

这道题就不一样,会影响前面的,那我们就看做是i为作用点,i+1,i+2为附带效应点,就可以转换成上面那种类型了。只是要在位置0的地方枚举是否要翻转，在位置20判断。

代码

 #include<set>

 #include<map>

 #include<queue>

 #include<stack>

 #include<cmath>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define RG register int

 #define rep(i,a,b)    for(RG i=a;i<=b;++i)

 #define per(i,a,b)    for(RG i=a;i>=b;--i)

 #define ll long long

 #define inf (1<<29)

 using namespace std;

 int n,ans,A;

 int num[],f[];

 inline int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 int main()

 {

     freopen("a","r",stdin);

     freopen("b","w",stdout);

     n=;

     rep(i,,)    num[i]=read();

     {

         f[]=,A=;

         if((num[]+f[])&)    f[]=,A++;

         rep(i,,)

             if((f[i-]+f[i-]+num[i])&)    f[i]=,A++;

         if((f[]+f[]+num[])&)    A=inf;

     }

     {

         memset(f,,sizeof(f));

         if((num[]+f[])&)    f[]=,ans++;

         rep(i,,n)

             if((f[i-]+f[i-]+num[i])&)    f[i]=,ans++;

         if((f[]+f[]+num[])&)    ans=inf;

     }

     if((f[]+f[]+num[])&)cout<<inf;

     else cout<<min(ans,A);

     return ;

 }