資源限制

內存限制：256.0MB ? C/C++時間限制：1.0s ? Java時間限制：3.0s ? Python時間限制：5.0s

問題描述

　　24點游戲是一個非常有意思的游戲，很流行，玩法很簡單：給你4張牌，每張牌上有數字（其中A代表1，J代表11，Q代表12，K代表13），你可以利用數學中的加、減、乘、除以及括號想辦法得到24，例如：
　　((A*K)-J)*Q等價于((1*13)-11)*12=24
　　加減乘不用多說了，但除法必須滿足能整除才能除！這樣有一些是得不到24點的，所以這里只要求求出不超過24的最大值。

輸入格式

　　輸入第一行N(1<=N<=5)表示有N組測試數據。每組測試數據輸入4行，每行一個整數(1到13)表示牌值。

輸出格式

　　每組測試數據輸出一個整數，表示所能得到的最大的不超過24的值。

樣例輸入

3
3
3
3
3
1
1
1
1
12
5
13
1

樣例輸出

24
4
21

#include<iostream>
using namespace std;
int a[4];
int ans;
//在有n個數的數組a中，尋找最大的不超過24的數 
void dfs(int* a,int n){if(n==1){if(a[0]<=24){ans=max(ans,a[0]);}return ;} for(int i=0;i<n-1;i++){for(int j=i+1;j<n;j++){int x=a[i],y=a[j];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]=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!=0&&x%y==0){//除法 a[j]=x/y;a[i]=a[n-1];dfs(a,n-1);}if(x!=0&&y%x==0){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 i=0;i<4;i++){scanf("%d",&a[i]); }ans=0;dfs(a,4);printf("%d\n",ans);}return 0;
} 

?思路：dfs深搜。先取兩個數進行運算，將運算后的結果看成是一個數，所以現在相當于有3個數進行24點。再在這3個數中取兩個數進行運算，運算后相當于只有2個數，將這2個數進行24點，得到1個數，即結果a[0]。取a[0]的最大值，即答案。

int x=a[i],y=a[j];a[j]=x+y;//加法 
a[i]=a[n-1];
dfs(a,n-1);

這里取a[i]，a[j]這兩個數進行運算，運算后這兩個數就沒用了，所以a[j]用來存運算結果，a[i]用來存a[n-1]，因為dfs(a，n-1)中相當于只取了前n-1個數，為了讓第n個數a[n-1]也參與運算，所以將a[n-1]存入a[i]。

如:1?4 6 8

一輪后有效數字：5 6 8

數組中表示：8 5 6 8

因為dfs(a，n-1)，所以其中最后一個數取不到，但是已經將它存到了最前面