Run ID | User | Problem | Result | Memory | Time | Language | Code Length | Submit Time |
6698372 | kingpro | 1020 | Accepted | 232K | 16MS | C++ | 1161B | 2010-04-07 01:55:14 |
1 #include <iostream>
2 using namespace std;
3
4 int each[16]={0}, sqs[40]={0};
5 int square=0, count=0, j=0, m=0, total=0;
6 int cmp(const void *a, const void *b) { return *(int *)b-*(int *)a; }
7 bool DFS(int n)
8 {
9 if(n>count) return true;
10 int tmp=0, tmpS=41;
11 for(j=0; j<square && (sqs[j]<tmpS && (tmpS=sqs[j], tmp=j), true); j++);
12 for(j=tmp+1; j<square && sqs[j]==tmpS; j++);
13 for(int k=0, eachk=11, maxS=j-tmp, maxX=square-tmpS, min=maxS>maxX ? maxX : maxS; k<count; k++)
14 if(each[k]!=0 && eachk!=each[k] && each[k]<=min)
15 {
16 eachk=each[k];
17 for(m=0; (m<eachk && (sqs[tmp+m]+=eachk, true)) || (each[k]=0, false); m++);
18 if(DFS(n+1)) return true;
19 for(m=0; (m<eachk && (sqs[tmp+m]-=eachk, true)) || (each[k]=eachk, false); m++);
20 }
21 return false;
22 }
23 int main()
24 {
25 int n=0; cin>>n;
26 while(n--)
27 {
28 for(cin>>square>>count, j=0, total=0; j<count && (cin>>each[j], total+=each[j]*each[j], true); j++);
29 if(square*square!=total && (cout<<"HUTUTU!"<<endl, true)) continue;
30 for(j=0; j<square && (sqs[j]=0, true); j++);
31 cout<<(qsort(each, count, sizeof(each[0]), cmp), DFS(1) ? "KHOOOOB!" : "HUTUTU!")<<endl;
32 }
33 return 0;
34 }
35
恩……DFS
选取N*N的最左上角未填充方块,按照小方块从大到小进行试填充。