Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:数据太弱,暴力搜索不剪枝AC！

Posted by topcheer at 2010-06-17 18:56:17 on Problem 1020
In Reply To:数据太弱,暴力搜索不剪枝AC！ Posted by:boycott at 2008-10-22 22:42:19
```> 10
> 21 16 5 7 2 4 8 9 4 2 3 2 4 2 9 6 4 4
> 28 16 10 10 7 3 5 9 10 3 8 5 7 7 5 7 1 7
> 13 11 1 2 2 8 1 2 3 7 1 4 4
> 23 16 1 7 5 8 5 10 9 2 1 4 2 6 3 1 8 7
> 26 16 3 7 10 9 8 3 1 9 6 6 8 2 10 1 5 4
> 21 16 6 5 10 4 2 3 4 7 7 2 3 3 1 1 7 8
> 18 14 2 6 3 1 2 3 9 9 4 5 7 2 1 2
> 15 12 3 1 3 1 8 1 5 1 6 2 6 3
> 22 15 2 6 8 5 4 7 9 9 4 5 4 3 6 3 4
> 22 14 4 1 6 7 9 1 7 3 10 8 1 6 5 4
>
> HUTUTU!
> HUTUTU!
> HUTUTU!
> KHOOOOB!
> KHOOOOB!
> KHOOOOB!
> KHOOOOB!
> HUTUTU!
> HUTUTU!
> KHOOOOB!
>
> 基本思路就是从左到右,从上往下，枚举每个小正方形放进去。
> #include<iostream>
> using namespace std;
> int c[11],d[41],s,n,sum;
> bool ok;
> void dfs(int a)
> {
> 	int i,j,put,p;
> 	bool f;
> 	if(a==n) {ok=true;exit;}
> 	for(i=1,put=41;i<=s;i++)
> 		if(d[i]<put) {put=d[i];p=i;}
> 	for(i=10;i>=1;i--)
> 		if(c[i]>0 && put+i-1<=s && p+i-1<=s)
> 		{
> 			for(j=p,f=true;j<=p+i-1;j++)
> 				if(d[j]>put) {f=false;break;}
> 			if(f)
> 			{
> 				for(j=p;j<=p+i-1;j++) d[j]+=i;
> 				c[i]--;
> 				dfs(a+1);
> 				c[i]++;
> 				for(j=p;j<=p+i-1;j++) d[j]-=i;
> 			}
> 		}
> }
> int main()
> {
> 	int t,it,i,tp;
> 	cin>>t;
> 	for(it=1;it<=t;it++)
> 	{
> 		cin>>s>>n;
> 		memset(c,0,sizeof(c));
> 		for(i=1;i<=40;i++) d[i]=1;
> 		sum=0;
> 		for(i=1;i<=n;i++)
> 		{
> 			cin>>tp;
> 			c[tp]++;
> 			sum+=tp*tp;
> 		}
> 		if(sum!=s*s) ok=false;
> 		else {ok=false;dfs(0);}
> 		if(ok) cout<<"KHOOOOB!"<<endl;
> 		else cout<<"HUTUTU!"<<endl;
> 	}
> 	system("pause");
> 	return 0;
> }
```

Followed by: