首页 > > 程序设计 > C/C++ >

【rqnoj 74】24点

2018-06-17 21:45:37来源：未知阅读 ()

题目描述

superwyh是一个非常疯狂的24点爱好者，空闲时总是自己拿出扑克来算24点，24点的规则很简单，就是给你4张扑克（从1至13，用A代替1，J代替11，Q代替12，K代替13）通过加减乘除来求得24，各位oier帮了superwyh好多忙，为了报答大家superwyh就和大家做个24点的游戏，superwyh给大家4张牌大家告诉superwyh能不能凑成24就行。

[renqing PS:这道题很easy，是送分的题]

输入格式4张牌的牌面（1<=n<=13）。

输出格式如果能凑成输出”yes”反之输出”no”。

样例输入

A 2 3 4

输出

yes

DP会Wa，就不粘代码了。

搜索AC

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 string s;int a[5];
 7 bool used[5];
 8 bool dfs(int dep,double sum){
 9     if(dep==4){
10         if(sum>23.999999&&sum<24.000001) return true;
11         else return false;
12     }
13     else{
14         for(int i=0;i<4;i++){
15             if(!used[i]){
16                 used[i]=1;
17                 if(dfs(dep+1,sum+a[i])) return true;
18                 if(dfs(dep+1,sum-a[i])) return true;
19                 if(dfs(dep+1,a[i]-sum)) return true;
20                 if(sum!=0&&dfs(dep+1,sum*a[i])) return true;
21                 if(sum!=0&&dfs(dep+1,sum/a[i])) return true;
22                 if(sum!=0&&dfs(dep+1,a[i]/sum)) return true;
23                 used[i]=0;
24             }
25         }
26         return false;
27     }
28 }
29 int main(){
30     for(int i=0;i<4;i++){
31         cin>>s;
32         if(s[0]=='A') a[i]=1;
33         else if(s[0]=='J') a[i]=11;
34         else if(s[0]=='Q') a[i]=12;
35         else if(s[0]=='K') a[i]=13;
36         else if(s[0]=='1'&&s[1]=='0') a[i]=10;
37         else a[i]=s[0]-'0';
38     }
39     if(dfs(0,0)) printf("yes\n");
40     else printf("no\n");
41     return 0;
42 }