描述
爱好探险的你，找到一座装满了宝藏的迷宫的入口，你看到入口的大门上有一个边长为s的正方形的大锁，旁边散落着n块正方形的金属小片，你意识到锁的钥匙，即是用这n小块，拼成大门上的正方形，你想知道是否能拼成这把钥匙打开迷宫的大门。
输入
输入包含多组数组，第一行是一个整数t（1 <= t <= 10)，表示有t组数据。接下里每组数组包含整数s，即锁的边长，整数n（1 <= n <= 16)，即金属小片的数量，接下来n个整数，分别是各个小片的边长ci（1 <= ci <= 10）。
输出
每组数据输出一行，输出“YES”或者”NO”，表示是否可以打开大门。
sol
一道比较有技巧性的搜索题
如果按小块搜索，每个小块放置的位置有很多种可能，状态过多
搜索每一个位置应该放哪片小块，就很好实现了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int T,n,C,num[11],s[32][32];
bool Ans;
void init(){
for(int i=1;i<=10;i++)num[i]=0;
Ans=0;
}
bool pd(int x,int y,int xx,int yy){
if(xx>C||yy>C)return 0;
for(int i=x;i<=xx;i++)
for(int j=y;j<=yy;j++){
if(s[i][j])return 0;
}
return 1;
}
void col(int x,int y,int xx,int yy,int color){
for(int i=x;i<=xx;i++)
for(int j=y;j<=yy;j++){
s[i][j]=color;
}
}
void dfs(int x,int y){
if(Ans)return;
if(y>C)return dfs(x+1,1);
if(x==C+1){
Ans=1;return;
}
if(s[x][y])return dfs(x,y+1);
for(int i=1;i<=10;i++){
if(num[i]>0&&pd(x,y,x+i-1,y+i-1)){
col(x,y,x+i-1,y+i-1,1);
num[i]--;
dfs(x,y+1);
col(x,y,x+i-1,y+i-1,0);
num[i]++;
}
}
}
void work(){
init();
scanf("%d%d",&C,&n);
for(int i=1;i<=n;i++){
int t;
scanf("%d",&t);
num[t]++;
}
dfs(1,1);
puts(Ans?"YES":"NO");
}
int main(){
scanf("%d",&T);
while(T--)work();
return 0;
}
/*
1
4 8 1 1 1 1 1 3 1 2
*/
