微信公众号个人可以做网站么,专业营销策划团队,免费发布网站建设信息,wordpress调用标题资源限制
内存限制#xff1a;256.0MB C/C时间限制#xff1a;1.0s Java时间限制#xff1a;3.0s Python时间限制#xff1a;5.0s
问题描述 24点游戏是一个非常有意思的游戏#xff0c;很流行#xff0c;玩法很简单#xff1a;给你4张牌#xff0c;每张牌上有数…资源限制
内存限制256.0MB C/C时间限制1.0s Java时间限制3.0s Python时间限制5.0s
问题描述 24点游戏是一个非常有意思的游戏很流行玩法很简单给你4张牌每张牌上有数字其中A代表1J代表11Q代表12K代表13你可以利用数学中的加、减、乘、除以及括号想办法得到24例如 ((A*K)-J)*Q等价于((1*13)-11)*1224 加减乘不用多说了但除法必须满足能整除才能除这样有一些是得不到24点的所以这里只要求求出不超过24的最大值。
输入格式 输入第一行N(1N5)表示有N组测试数据。每组测试数据输入4行每行一个整数(1到13)表示牌值。
输出格式 每组测试数据输出一个整数表示所能得到的最大的不超过24的值。
样例输入
3 3 3 3 3 1 1 1 1 12 5 13 1
样例输出
24 4 21
#includeiostream
using namespace std;
int a[4];
int ans;
//在有n个数的数组a中寻找最大的不超过24的数
void dfs(int* a,int n){if(n1){if(a[0]24){ansmax(ans,a[0]);}return ;} for(int i0;in-1;i){for(int ji1;jn;j){int xa[i],ya[j];a[j]xy;//加法 a[i]a[n-1];dfs(a,n-1);a[j]x*y;//乘法 a[i]a[n-1];dfs(a,n-1);a[j]x-y;//减法 a[i]a[n-1];dfs(a,n-1);a[j]y-x;a[i]a[n-1];dfs(a,n-1);if(y!0x%y0){//除法 a[j]x/y;a[i]a[n-1];dfs(a,n-1);}if(x!0y%x0){a[j]y/x;a[i]a[n-1];dfs(a,n-1);}a[i]x;a[j]y;}}
}
int main(){int n;scanf(%d,n);while(n--){for(int i0;i4;i){scanf(%d,a[i]); }ans0;dfs(a,4);printf(%d\n,ans);}return 0;
} 思路dfs深搜。先取两个数进行运算将运算后的结果看成是一个数所以现在相当于有3个数进行24点。再在这3个数中取两个数进行运算运算后相当于只有2个数将这2个数进行24点得到1个数即结果a[0]。取a[0]的最大值即答案。
int xa[i],ya[j];a[j]xy;//加法
a[i]a[n-1];
dfs(a,n-1);
这里取a[i]a[j]这两个数进行运算运算后这两个数就没用了所以a[j]用来存运算结果a[i]用来存a[n-1]因为dfs(an-1)中相当于只取了前n-1个数为了让第n个数a[n-1]也参与运算所以将a[n-1]存入a[i]。
如:1 4 6 8
一轮后有效数字5 6 8
数组中表示8 5 6 8
因为dfs(an-1)所以其中最后一个数取不到但是已经将它存到了最前面
