C++-POJ1020-Anniversary Cake[搜索][dfs]

 1 #include <set>
 2 #include <map>
 3 #include <cmath>
 4 #include <queue>
 5 #include <vector>
 6 #include <cstdio>
 7 #include <cstdlib>
 8 #include <cstring>
 9 #include <iostream>
10 #include <algorithm>
11 using namespace std;
12 int t,s,n,a,sum,row[41],cake[17];
13 void init(){memset(row,0,sizeof(row)),memset(cake,0,sizeof(cake)),sum=0;}
14 int find(){int p;for(int i=1,min=41;i<=s;i++)if(min>row[i])min=row[i],p=i;return p;}
15 int count(int p){int cnt=0;for(int i=p;i<=s;i++)if(row[i]==row[p])cnt++;else break;return cnt;}
16 void put(int p,int x){cake[x]--;for(int i=p;i<=p+x-1;i++)row[i]+=x;}
17 void del(int p,int x){cake[x]++;for(int i=p;i<=p+x-1;i++)row[i]-=x;}
18 bool dfs(int dep) {
19     if(dep==n)return true;int p=find();
20     for(int x=10;x;x--)if(cake[x]&&row[p]+x<=s&&count(p)>=x){put(p,x);if(dfs(dep+1))return true;del(p,x);}
21     return false;
22 }
23 int main() {
24     for (scanf("%d",&t);t--;) {
25         init(),scanf("%d%d",&s,&n);
26         for(int i=1;i<=n;i++)scanf("%d",&a),cake[a]++,sum+=a*a;
27         puts((sum==s*s?dfs(0):0)?"KHOOOOB!":"HUTUTU!");
28     }
29     return 0;
30 }
~~Jason_liu O(∩_∩)O