本文主要是介绍HDU2209 翻纸牌游戏【技巧】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2209
题目大意：
有N张牌，有正面朝上的，也有反面朝上的，现在需要把所有牌都正面朝上，已知每翻一张纸牌，
该纸牌左右两侧各一张纸牌也跟着翻动。现在给你一行只包含字符'0'和'1'的01字符串，'1'代表纸牌
反面，'0'代表纸牌正面。现在需要将字符串变为全为"0000…00"的字符串，一次操作只能改变一个
字符本身和它左右两侧各一个字符，问：最少要经过多少次操作，才能使字符串变为"0000…00"。
如果不能翻成"0000…00"的状态，则输出"NO"。
思路：
可以直接想到用广搜来找最小步数。但是观察后发现可以从前到后模拟一下就可以得到结果了。
因为从左向右翻纸牌，对于当前纸牌，只要当前纸牌左侧的纸牌为'1'，就不用翻动该纸牌，如果左侧纸
牌为'0'，则必须翻动纸牌。而对于第一张纸牌来说，没有左侧纸牌，所以上述判断从第2张纸牌开始，
而第一张纸牌有翻与不翻的两种情况，将这两种情况分别考虑。最后递推到最后一张纸牌，这时，除最
最后一张纸牌外，其余牌都已经变为"0000……0"，只需要判断最后一张纸牌是不是'0'，就可以知道是不
是能够翻成"0000…00"状态了。如果两者都不能翻成这种状态，则结果输出"NO"，否则，输出能翻出的
情况中最小的情况。
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;char s[22],a[22],b[22];int Min,Numa,Numb,Num,len,flag;void solveA()
{Num = 0;for(int i = 1; i < len; ++i){if(a[i-1] == '1'){a[i-1] = '0';if(a[i] == '0')a[i] = '1';elsea[i] = '0';if(i != len-1){if(a[i+1] == '0')a[i+1] = '1';elsea[i+1] = '0';}Num++;}}if(a[len-1] == '0'){Numa = Num;flag = 1;}
}void solveB()
{Num = 0;if(b[0] == '1')b[0] = '0';elseb[0] = '1';if(b[1] == '1')b[1] = '0';elseb[1] = '1';Num++;for(int i = 1; i < len; ++i){if(b[i-1] == '1'){b[i-1] = '0';if(b[i] == '0')b[i] = '1';elseb[i] = '0';if(i != len-1){if(b[i+1] == '0')b[i+1] = '1';elseb[i+1] = '0';}Num++;}}if(b[len-1] == '0'){Numb = Num;flag = 1;}
}int main()
{while(cin >> s){len = strlen(s);memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(int i = 0; i < len; ++i)a[i] = b[i] = s[i];flag = 0;Numa = Numb = 0xffffff0;solveA();solveB();if(len == 1){if(s[0] == '1')cout << '1' << endl;elsecout << '0' << endl;continue;}if(flag == 0)cout << "NO" << endl;else{if(Numa < Numb)cout << Numa << endl;elsecout << Numb << endl;}}return 0;
}这篇关于HDU2209 翻纸牌游戏【技巧】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
