首页 > 代码库 > HDOJ 2209 贪心
HDOJ 2209 贪心
翻纸牌游戏
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3669 Accepted Submission(s): 1371
Problem Description
有一种纸牌游戏,很有意思,给你N张纸牌,一字排开,纸牌有正反两面,开始的纸牌可能是一种乱的状态(有些朝正,有些朝反),现在你需要整理这些纸牌。但是麻烦的是,每当你翻一张纸牌(由正翻到反,或者有反翻到正)时,他左右两张纸牌(最左边和最右边的纸牌,只会影响附近一张)也必须跟着翻动,现在给你一个乱的状态,问你能否把他们整理好,使得每张纸牌都正面朝上,如果可以,最少需要多少次操作。
Input
有多个case,每个case输入一行01符号串(长度不超过20),1表示反面朝上,0表示正面朝上。
Output
对于每组case,如果可以翻,输出最少需要翻动的次数,否则输出NO。
Sample Input
01
011
Sample Output
NO
1
Author
wangye
题解:
首先有两个分支,即第一张牌翻还是不翻(它的前面没有牌,所以两种可能都要考虑),之后往后dfs,去看这张牌的前面一张牌是正面还是反面,如果是正面,那就不翻现在这张牌,否则,翻这张牌来把前面那张变成正面,变成正面后,没有其他操作会将它变回反面了,这样下去,当搜索结束之后,讨论最后一张牌,如果是正,那就这组存在解,否则,无解。
代码:
1 #include "cstdio" 2 #include "iostream" 3 #include "algorithm" 4 #include "string" 5 #include "cstring" 6 #include "queue" 7 #include "cmath" 8 #include "vector" 9 #include "map" 10 #include "stdlib.h" 11 #include "set" 12 #define mj 13 #define db double 14 #define ll long long 15 using namespace std; 16 const int N=1e6+5; 17 const int mod=1e9+7; 18 const ll inf=1e16+10; 19 char s[N]; 20 int a[N]; 21 int dfs(int i,int n,int cnt){ 22 if(i==n){//判断最后一张牌的状态 23 if(a[n-1]) return 1e8; 24 else return cnt; 25 } 26 if(a[i-1]) a[i-1]=!a[i-1],a[i]=!a[i],a[i+1]=!a[i+1],cnt++; 27 return dfs(i+1,n,cnt); 28 } 29 int main() 30 { 31 int n; 32 while(scanf("%s",s)==1){ 33 int ans; 34 n=strlen(s); 35 for(int i=0;i<n;i++) 36 a[i]=s[i]-‘0‘; 37 a[0]=!a[0],a[1]=!a[1]; 38 ans=dfs(1,n,1); 39 for(int i=0;i<n;i++) 40 a[i]=s[i]-‘0‘; 41 ans=min(ans,dfs(1,n,0));//取最小值 42 if(ans==1e8) printf("NO\n"); 43 else printf("%d\n",ans); 44 45 } 46 return 0; 47 }
HDOJ 2209 贪心
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。