题意:
给定一串01序列,用来表示牌的正反情况,每次操作可以使一个元素翻转(既1变为0,0变为1),它的相邻两个元素也会翻转。问至少需要多少次才能使所有的元素都为0.无法做到输出“NO”。
题解:
我们先考虑第一张牌的情况,我们发现第一张牌要翻的话只能翻第一张牌和翻第二张牌,而为了减少无谓的消耗,我们一张牌只能翻一次,就是贪心。那么之后的情况就是我们分别考虑第一张翻还是不翻,那么就推出第二张是否要翻,从而到第三张。。一直到最后一张。若最后一张还是反面朝上那说明无解,否则输出两种情况中的最优解。
代码:
#include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <map> #include <vector> using namespace std; const int maxn=22; const int INF=1e8; char a[maxn],b[maxn]; int n; char turn(char ch) { if(ch=='1')return '0'; return '1'; } int dfs(int t,int num) { if(t==n) { return b[t-1]=='1'?INF:num; } if(b[t-1]=='1') { b[t]=turn(b[t]); b[t+1]=turn(b[t+1]); num++; } return dfs(t+1,num); } int main() { while(scanf("%s",a)!=EOF) { n=strlen(a); strcpy(b,a); int ans=INF; ans=min(ans,dfs(1,0)); strcpy(b,a); b[0]=turn(b[0]); b[1]=turn(b[1]); ans=min(ans,dfs(1,0)+1); if(ans==INF)printf("NO\n"); else printf("%d\n",ans); } return 0; }