POJ3185 The Water Bowls

　　題目大意: 奶牛有20只碗擺成一排，用鼻子頂某只碗的話，包括左右兩只在內的一共三只碗會反向，現在給出碗的初始狀態，問至少要用鼻子頂多少次才能使所有碗都朝上

　　一開始試了一下dfs,由于對dfs還是不太熟悉,先是用了一個數組b[i]來儲存翻轉后的狀態,后來發現這個搜索的狀態雖然類似背包,要么翻轉,要么不翻轉,但是翻轉某個碗以后會對其他的也造成影響,所以這樣這樣做就錯了,可以只用原來的數組就ok了

????? 在上述問題解決后,又因為胡亂剪枝導致wa了幾次,一開始我想先對a[0]和a[19]進行判斷是否為1,來確定是否需要翻轉,這樣的話a[19]那兒的1可能是翻轉后形成的,這是進行翻轉就回不到原來的狀態,導致沒法遍歷2^n而wa,同時,對a[0]是否為1的判斷也是錯的,因為a[0]等于1時也可以通過翻轉a[1]來實現a[0]=0的要求,a[19]=1也可翻轉下一次的a[18].

不用任何優化頂多2^20(10的6次方左右),也可以過,我最后是250ms左右過的.

　　dfs代碼:(畢竟dfs的題做的比較少,也就先用dfs來練手了)(先翻轉再翻回來的dfs才是對的)

　　

#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <deque> #include <list> #include <set> #include <map> #include <stack> #include <queue> #include <numeric> #include <iomanip> #include <bitset> #include <sstream> #include <fstream> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define in(n) scanf("%d",&(n)) #define in2(x1,x2) scanf("%d%d",&(x1),&(x2)) #define inll(n) scanf("%I64d",&(n)) #define inll2(x1,x2) scanf("%I64d%I64d",&(x1),&(x2)) #define inlld(n) scanf("%lld",&(n)) #define inlld2(x1,x2) scanf("%lld%lld",&(x1),&(x2)) #define inf(n) scanf("%f",&(n)) #define inf2(x1,x2) scanf("%f%f",&(x1),&(x2)) #define inlf(n) scanf("%lf",&(n)) #define inlf2(x1,x2) scanf("%lf%lf",&(x1),&(x2)) #define inc(str) scanf("%c",&(str)) #define ins(str) scanf("%s",(str)) #define out(x) printf("%d\n",(x)) #define out2(x1,x2) printf("%d %d\n",(x1),(x2)) #define outf(x) printf("%f\n",(x)) #define outlf(x) printf("%lf\n",(x)) #define outlf2(x1,x2) printf("%lf %lf\n",(x1),(x2)); #define outll(x) printf("%I64d\n",(x)) #define outlld(x) printf("%lld\n",(x)) #define outc(str) printf("%c\n",(str)) #define pb push_back #define mp make_pair #define fi first #define se second #define SZ(x) ((int)(x).size()) #define mem(X,Y) memset(X,Y,sizeof(X)); typedef vector<int> vec; typedef long long ll; typedef pair<int,int> P; const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; const int INF=0x3f3f3f3f; const ll mod=1e9+7; ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} const bool AC=true;int a[25],b[25],ans; bool flag; void dfs(int i,int cnt){if(i==20){flag=true;rep(j,0,20){if(a[j]==1) {flag=false;break;}}if(flag){ans=min(ans,cnt);}return;}else if(i==0){a[i]=!a[i];a[i+1]=!a[i+1];dfs(i+1,cnt+1);a[i]=!a[i];a[i+1]=!a[i+1];dfs(i+1,cnt); //此處也不用判斷是否為1來剪枝,否則會wa }else if(i==19){a[i]=!a[i];a[i-1]=!a[i-1];dfs(i+1,cnt+1);a[i]=!a[i];a[i-1]=!a[i-1];dfs(i+1,cnt); //不要亂剪枝,否則翻轉不回來 }else{a[i]=!a[i];a[i-1]=!a[i-1];a[i+1]=!a[i+1];dfs(i+1,cnt+1);//先翻轉,再翻回來a[i]=!a[i];a[i-1]=!a[i-1];a[i+1]=!a[i+1];dfs(i+1,cnt);}return ; } int main(){rep(i,0,20) {in(a[i]);}ans=INF;dfs(0,0);out(ans);return 0; }

?下面是反轉法:考慮某個碗,翻轉下一個碗.

　　　　　　　如果某個碗是0,則這個碗不需要考慮,繼續考慮下一個碗,不斷向前推進區間;

　　　　　　　如果某個碗是1,則必須翻轉下一個碗,繼續考慮下一個碗,不斷向前推進區間;

　　　　　　　這樣復雜度就是O(n),類似尺取法的思想;

　　　　　　　　從對稱性的角度考慮問題

????　　 wa的注意了,不要通過判斷a[0]=0來確定是否需要反轉a[0],這樣是錯的如下面的情況: 0 0 1 0 0 0 0 0.....后面全是0,這時如果反轉a[0]需要2步,不翻轉a[0]需要12步(因為這個wa了n次),

　　　　所以不管a[0]為什么值都要嘗試一下是否需要反轉a[0],從對稱性來看,從左向右翻轉,a[19]要么翻轉,要么不翻轉,

　　　　所以翻轉法有兩種實現方式:從左向右翻轉兩次(反轉a[0]或者不反轉a[0])

? 　　　　　　　　　　　　　　　　從左向右翻轉一次(不翻轉a[0]),再從右向左翻轉一次(不翻轉a[19]);(讓某個碗翻轉的方式有兩種)

　從左向右翻轉兩次(反轉a[0]或者不反轉a[0])

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int a[20],b[20]; void turn(int i){b[i-1]^=1; b[i]^=1;if(i<19) b[i+1]^=1; } int main(){int cnt1=0,cnt2=0;for(int i=0;i<20;i++) scanf("%d",&a[i]);//反轉b[0];memcpy(b,a,sizeof(a));b[0]^=1;b[1]^=1;cnt1++; //此處要加1for(int i=0;i<19;i++){if(b[i]){turn(i+1);//考慮某個碗,反轉其后面的碗cnt1++;}}if(b[19]) cnt1=0x3f3f3f3f;//不反轉b[0];memcpy(b,a,sizeof(a));for(int i=0;i<19;i++){if(b[i]){turn(i+1);//考慮某個碗,反轉其后面的碗cnt2++;}}if(b[19]) cnt2=0x3f3f3f3f;printf("%d\n",min(cnt1,cnt2));return 0; }

從左向右翻轉一次(不翻轉a[0]),再從右向左翻轉一次(不翻轉a[19]);

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int a[20],b[20]; void turn1(int i){b[i-1]^=1; b[i]^=1;if(i<19) b[i+1]^=1; } void turn2(int i){a[i+1]^=1; a[i]^=1;if(i>0) a[i-1]^=1; } int main(){int cnt1=0,cnt2=0;for(int i=0;i<20;i++) scanf("%d",&a[i]);memcpy(b,a,sizeof(a));for(int i=0;i<19;i++){if(b[i]){turn1(i+1);//考慮某個碗,反轉其后面的碗cnt1++;}}if(b[19]) cnt1=0x3f3f3f3f;for(int i=19;i>0;i--){if(a[i]){turn2(i-1);//考慮某個碗,反轉其前面的碗cnt2++;}}if(a[19]) cnt2=0x3f3f3f3f;printf("%d\n",min(cnt1,cnt2));return 0; }

?

轉載于:https://www.cnblogs.com/akrusher/p/5353790.html

總結

以上是生活随笔為你收集整理的POJ3185 The Water Bowls(反转法or dfs 爆搜)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。