http://acm.pku.edu.cn/JudgeOnline/problem?id=2362很好很經(jīng)典的深搜題，減枝不好很容易TLE,注意搜索順序。先從大到小排序。這題跟1011差不多
1011黑書(shū)上有講。最重要的減枝就是不能重復(fù)搜索，所以函數(shù)是
int solve(int unused
,int start
,int left
)start就是拼當(dāng)前這一條邊的時(shí)候從那跟開(kāi)始搜起。left表示當(dāng)前這條邊還剩多少拼完
Source Code
| Problem: 2362 |
|
User: lovecanon |
| Memory: 204K |
|
Time: 16MS |
| Language: C |
|
Result: Accepted |
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int len[21];
int used[21];
int n;
int side;
int start;
int cmp(const void *a,const void *b)
{
return *(int *)b-*(int *)a;
}
int solve(int unused,int start,int left)
{
int i;
if(unused==0&&left==0) return 1;
if(unused==0) return 0;
if(left==0)
{
left=side;
for(i=1;i<=n&&used[i];i++)
if(solve(unused,i,side)) return 1;
}
for(i=start;i<=n;i++)
{
if(!used[i]&&len[i]<=left)
{
if(i>1)
{
if(len[i]==len[i-1]&&!used[i-1])
continue;
}
if(left<len[n]) continue;
used[i]=1;
if(solve(unused-1,i,left-len[i])) return 1;
used[i]=0;
if(len[i]==left||left==side) return 0;
}
}
return 0;
}
int main()
{
int T,sum,i;
scanf("%d",&T);
while(T--)
{
sum=0;
scanf("%d",&n);
len[0]=0x7fffffff;
for(i=1;i<=n;i++)
{
scanf("%d",&len[i]);
sum+=len[i];
}
if(sum%4) printf("no\n");
else
{
side=sum/4;
memset(used,0,sizeof(used));
qsort(len,n+1,sizeof(len[0]),cmp);
if(len[1]>side) printf("no\n");
else if(solve(n,1,side)) printf("yes\n");
else printf("no\n");
}
}
return 0;
}