![The Water Bowls [POJ3185] [开关问题] The Water Bowls [POJ3185] [开关问题]](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
题意
一串长度为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 ;
}