1201: 翻紙牌游戲

Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?87??Solved:?28
[Submit][Status][Web Board]

Description

有一種紙牌游戲，很有意思，給你N張紙牌，一字排開，紙牌有正反兩面，開始的紙牌可能是一種亂的狀態（有些朝正，有些朝反），現在你需要整理這些紙牌。但是麻煩的是，每當你翻一張紙牌（由正翻到反，或者有反翻到正）時，他左右兩張紙牌（最左邊和最右邊的紙牌，只會影響附近一張）也必須跟著翻動，現在給你一個亂的狀態，問你能否把他們整理好，使得每張紙牌都正面朝上，如果可以，最少需要多少次操作。

Input

有多個case，每個case輸入一行01符號串（長度不超過1000），1表示反面朝上，0表示正面朝上。

Output

對于每組case，如果可以翻，輸出最少需要翻動的次數，否則輸出NO。

Sample Input

010111111

Sample Output

NO12

HINT

對于第一組測試數據，無論怎樣操作，都無法完成.

對于第二組測試數據，只需反轉一次最右面的牌即可

對于第三組測試數據，需要翻轉第一張牌和最后一張牌

***請使用scanf("%s",s)輸入，使用gets()可能會遇到麻煩

Source

思路：兩遍的dfs，

思路：對于1的一定要翻轉，所以可以分兩種情況對于第一張牌翻轉，則接下去改變的牌為1的就要翻轉。對于第一張牌不翻轉，接下去的牌繼續判斷翻轉不翻轉。然后取最小值，若沒有最小值，則說明不能完全翻轉正面。代碼：#include<cstdio> #include<queue> #include<cstring> #include<algorithm> using namespace std;#define inf 0x3f3f3f3 char s[1010]; int a[1010];int dfs(int i,int len,int m) {if(i==len)return a[i-1]?inf:m;if(a[i-1]){a[i-1] = !a[i-1];a[i] = !a[i];a[i+1] = !a[i+1];m++;}dfs(i+1,len,m); } int main() {while(~scanf("%s",s)){int len=strlen(s);for(int i=0; i<len; i++)a[i]=s[i]-'0';int ans=inf;a[0]=!a[0];//先翻轉前兩張牌，目的是第一次的dfs要翻轉第一張牌。a[1]=!a[1];ans=min(ans,dfs(1,len,1));for(int i=0; i<len; i++)a[i]=s[i]-'0';ans=min(ans,dfs(1,len,0));if(ans==inf)printf("NO\n");else printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的zcmu-1201的全部內容，希望文章能夠幫你解決所遇到的問題。

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