例.給定一個(gè)01串，現(xiàn)有翻轉(zhuǎn)規(guī)則：翻轉(zhuǎn)某一個(gè)位置時(shí)其后面2個(gè)位置也會(huì)跟著翻轉(zhuǎn)，也就是每次翻轉(zhuǎn)都會(huì)翻轉(zhuǎn)3個(gè)連續(xù)的位置。要將01串全部翻轉(zhuǎn)為0，求最小的翻轉(zhuǎn)次數(shù) 形似這類題的問(wèn)題叫做翻轉(zhuǎn)問(wèn)題，也可以叫開(kāi)關(guān)問(wèn)題，對(duì)于這類題通常有以下的特點(diǎn)，思考一下就可以想到。
**1.交換區(qū)間得反轉(zhuǎn)順序隊(duì)結(jié)果沒(méi)有影響。 2.此外可以知道對(duì)于同一個(gè)區(qū)間進(jìn)行兩次以上得反轉(zhuǎn)是多余的。 3.由此，反轉(zhuǎn)問(wèn)題（也叫開(kāi)關(guān)問(wèn)題）就轉(zhuǎn)化成求反轉(zhuǎn)區(qū)間的集合，常常和枚舉一起服用。**
比如以下的題目：
poj3276
題意： N個(gè)牛 每個(gè)都有一定的方向 B背對(duì) F表示頭對(duì)著你 給你一個(gè)裝置 每次可以選擇連續(xù)的K個(gè)牛反轉(zhuǎn)方向 問(wèn)你如何選擇K 使得操作數(shù)最少 k也應(yīng)盡量小. 思路：
定義 f[i]:區(qū)間[i,i+k-1]進(jìn)行反轉(zhuǎn)的話就為1，否則為0
區(qū)間反轉(zhuǎn)部分很好優(yōu)化： 在考慮第i頭牛時(shí)候，如果
所以這個(gè)每一次都可以用常數(shù)算出來(lái)，時(shí)間復(fù)雜度O（n^2）
#include<cstdio>#include<cstring>#include<iostream>using namespace std;const int N=5000+10;int f[N],dir[N],n;int solve(int k){ int cnt=0,sum=0;//sum為f的和 memset(f,0,sizeof(f)); for(int i=1;i<=n-k+1;i++){ if((dir[i]+sum)%2){ cnt++; f[i]=1; } sum+=f[i]; if(i-k+1>=1) sum-=f[i-k+1]; } for(int i=n-k+2;i<=n;i++){//檢查剩下的牛有沒(méi)有朝后面的情況 if((dir[i]+sum)%2) return n+1; if(i-k+1>=1) sum-=f[i-k+1]; } return cnt;}int main(){ while(~scanf("%d",&n)){ for(int i=1;i<=n;i++){ char c;scanf(" %c",&c); if(c=='B') dir[i]=1; } int ansk,ansm=n,t; for(int i=1;i<=n;i++){ t=solve(i); if(t<ansm){ ansm=t;ansk=i; } } poj3279 題意： 一個(gè)M*N的黑白棋棋盤(pán)擺滿棋子，每次操作可以反轉(zhuǎn)一個(gè)位置和其上下左右共五個(gè)位置的棋子的顏色，求要使用最少翻轉(zhuǎn)次數(shù)將所有棋子反轉(zhuǎn)為黑色所需翻轉(zhuǎn)的是哪些棋子. 思路： 在上面的那道題，讓最左端的奶牛反轉(zhuǎn)的情況只有一種，于是直接判斷的方法就可以確定，但是這里不一樣，比如，看最左上面的角，除了反轉(zhuǎn)（1，1），（1，2），（2，1）都可以導(dǎo)致他翻裝。 于是不妨我們先確定最上面一行的反裝方式，此時(shí)能反轉(zhuǎn)(1,1)只有（2，1）， 所以如果已知第一行就可以知道第二行那些點(diǎn)需要反轉(zhuǎn)。這樣反復(fù)下去，只要最后一行全部為白，就說(shuō)明可行。 那么這個(gè)算法時(shí)間復(fù)雜度是(N*M*2^N).#include<cstdio>#include<cstring>using namespace std;const int dx[5]={-1,0,0,0,1};const int dy[5]={0,-1,0,1,0};int m,n,M[20][20],tmp[20][20],ans[20][20],cnt;int get(int x,int y){ int t=M[x][y]; for(int i=0;i<5;i++){ int tx=dx[i]+x,ty=dy[i]+y; if(tx>=0&&tx<m&&ty>=0&&ty<n) t+=tmp[tx][ty]; } return t%2;}int cal(){ for(int i=1;i<m;i++){ for(int j=0;j<n;j++){ if(get(i-1,j)) tmp[i][j]=1; } } for(int j=0;j<n;j++){ if(get(m-1,j)!=0) return n*m+1; } int res=0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ res+=tmp[i][j]; } } return res;}int main(){ while(~scanf("%d%d",&m,&n)){ cnt=n*m+1; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ scanf("%d",&M[i][j]); } } for(int i=0;i<(1<<n);i++){ memset(tmp,0,sizeof(tmp)); for(int j=0;j<n;j++){ tmp[0][j]=i>>j&1; } int t=cal(); if(t<cnt){ cnt=t; memcpy(ans,tmp,sizeof(tmp)); } } if(cnt==n*m+1){ printf("IMPOSSIBLE/n"); } else{ for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ printf("%d%c",ans[i][j],j+1==n ? '/n':' '); } } } }}poj3185 題意： 翻蓋有獎(jiǎng)：將一列碗翻成口朝上，一把下去可能同時(shí)反轉(zhuǎn)3個(gè)或2個(gè)（首尾），求最小翻轉(zhuǎn)次數(shù)。
思路： 這題分析一下，可以知道選擇從第一個(gè)開(kāi)始翻，還是聰?shù)诙€(gè)開(kāi)始翻，會(huì)導(dǎo)致兩種不同的狀態(tài)和結(jié)果，但都是唯一的。所以就枚舉第一個(gè)還是第二個(gè)開(kāi)始翻，然后從左往右依次判斷，接下來(lái)每個(gè)點(diǎn)需不需要翻轉(zhuǎn)取決它左邊是不是朝下。
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int dir[25],f[25];int main(){ while(~scanf("%d",&dir[0])){ int tmp=0,ans=20; memset(f,0,sizeof(f)); for(int i=1;i<20;i++) scanf("%d",&dir[i]); f[0]=1;tmp++; for(int i=1;i<20;i++){ if(f[i]=(f[i-2]^f[i-1]^dir[i-1])) tmp++; } if((f[18]^f[19]^dir[19])==0&&tmp<ans) ans=tmp; tmp=0;f[0]=0; for(int i=1;i<20;i++){ if(f[i]=(f[i-2]^f[i-1]^dir[i-1])) tmp++; } if(f[18]^f[19]^dir[19]==0&&tmp<ans) ans=tmp; printf("%d/n",ans); }}poj1222
題意： 有一個(gè)5 * 6的矩陣，每個(gè)位置表示燈，1表示燈亮，0表示燈滅。 然后如果選定位置i，j點(diǎn)擊，則位置i，j和其上下左右的燈的狀態(tài)都會(huì)反轉(zhuǎn)。 現(xiàn)在要你求出一個(gè)5 * 6的矩陣，1表示這個(gè)燈被點(diǎn)擊過(guò)，0表示沒(méi)有。 要求這個(gè)矩陣能夠使得原矩陣的燈全滅。
思路： 和poj3279一模一樣
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int m[8][8],f[8][8],as[8][8],dir[5][5]={-1,0,0,0,0,1,1,0,0,-1};int get(int x,int y){ int c=m[x][y]; for(int i=0;i<5;i++){ int tx=x+dir[i][0]; int ty=y+dir[i][6]; c+=f[tx][ty]; } return c%2;}int calc(){ for(int i=1;i<5;i++){ for(int j=0;j<6;j++){ if(get(i-1,j)==1){ f[i][j]=1; } } } for(int j=0;j<6;j++){ if(get(4,j)!=0) return 30; } int res=0; for(int i=0;i<5;i++){ for(int j=0;j<6;j++){ res+=f[i][j]; } } return res;}int main(){ int T,cnt=1;scanf("%d",&T); while(T--){ for(int i=0;i<5;i++){ for(int j=0;j<6;j++) scanf("%d",&m[i][j]); } int ans=31; for(int i=0;i<1<<6;i++){ memset(f,0,sizeof(f)); for(int j=0;j<6;j++){ f[0][6-j-1]=i>>j&1; } int num=calc(); if(num<ans){ ans=num; memcpy(as,f,sizeof(f)); } } printf("PUZZLE #%d/n",cnt++); for(int i=0;i<5;i++){ for(int j=0;j<6;j++){ printf("%d%c",as[i][j],j==5? '/n':' '); } } }}后記：往往開(kāi)關(guān)問(wèn)題可以轉(zhuǎn)換成矩陣求解一組方程的解是否存在，用高斯消元求解，并且通過(guò)這些分析知道，當(dāng)自由變員不超過(guò)N個(gè)時(shí)候，也可以用來(lái)求解最優(yōu)解。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
