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

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

Posted by yayu_myself at 2009-08-10 12:22:03 on Problem 1020 and last updated at 2009-09-04 10:06:23
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;
> }

for(i=10;i>=1;i--)
if(c[i]>0 && put+i-1<=s && p+i-1<=s)

#include <stdio.h>
#include <memory.h>
int cakeside,piecenum,pieces[11];
//fillednum stand for the nums had filled
bool fill(int fillednum,int* used)
{
//如果已填的个数等于需求的蛋糕个数则表示刚好
if(fillednum==piecenum)
return true;
int i,j,minusedrow=41,nowcol=0;
//寻找未填的行数最小的那列
for(i=1;i<=cakeside;i++)
{
if(used[i]<minusedrow)
{
minusedrow = used[i];
nowcol = i;
}
}
//从行数最小的那列开始，从大到小搜索能填入的蛋糕
for(i=10;i>0;--i)
{
if(pieces[i]>0 && i+minusedrow<=cakeside+1 && i+nowcol<=cakeside+1)
{
bool flag=true;
//判断连续的区域是否能放下当前蛋糕
for(j=nowcol;j<nowcol+i;j++)
{
if(used[j]>minusedrow)
{
flag=false;
break;
}
}
if(flag)
{
//能放下则更新蛋糕所在的列的已填行数
for(j=nowcol;j<nowcol+i;j++)
used[j] += i;
//当前大小蛋糕数减一
pieces[i]--;
//继续切下一块蛋糕
if(fill(fillednum+1,used))
return true;
//到这说明上面方案不可行，回溯，不能切当前大小的蛋糕
pieces[i]++;
for(j=nowcol;j<nowcol+i;j++)
used[j] -= i;
}
}
}
return false;
}
int main()
{
int ncase,i,j;
scanf("%d",&ncase);
while(ncase>0)
{
--ncase;
int sum=0;
int pieceside;
scanf("%d %d",&cakeside,&piecenum);
memset(pieces,0,sizeof(pieces));
//记录各不同大小的蛋糕个数，大小范围在1-10之间
for(i=0;i<piecenum;++i)
{
scanf("%d",&pieceside);
//大小为pieceside的个数
pieces[pieceside]++;
sum += pieceside*pieceside;
}
if(sum!=cakeside*cakeside)
{
printf("HUTUTU!\n");
continue;
}
bool IsWaste=true;
//used[i]记录的是第i列还没填的那行
int used[41];
for(i=1;i<=40;i++) used[i]=1;
//fill表示从第几块蛋糕开始填是否能刚好填满所有蛋糕
IsWaste = !fill(0,used);
if(IsWaste)
printf("HUTUTU!\n");
else
printf("KHOOOOB!\n");

}
return 0;
}

PS：感觉在网页看代码太乱。。ctrl+v到notepad2看着舒服。。嘿嘿。。```

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator