题意:
给你4-20根小木棍,你需要尝试用这些木棍拼接成一个正方形,要求不能多用/少用/折断。多组数据。
这似乎是一道很经典的DFS+剪枝的题目?
首先我们统计sum,看看是不是4的倍数。(这个特判是小学生特判?)
我们直接DFS。递归终点为所有边全部用完,并且递归过程中不能有一根木棒横跨两边。
上图中彩色的线段表示小木棍,黑色长线段表示正方形周长4a,每一个被端点分割的短线段表示正方形边长a。
可以看到,绿线由于没有越过端点所以合法(没有折断),棕线由于越过了第二个端点(跨越二,三 两边)所以折断了,所以不合法。
然后愉快地提交,TLE。
考虑优化。我们发现,如果我们拼出来了3条边,那第四条边我们也不用去拼了。于是把递归终点转换为当前已经拼接的长度是正方形边长的3倍(正方形周长的3/4)。(所以这是可行性剪枝还是最优性剪枝?在线等,急)
然而还是TLE。
看了一堆博客以后,考虑第二个优化:
如果一根木棒在拼接某一条边的时候已经被pass了,说明在拼接这条边是不可能再用到(因为已经pass了嘛,说明这木棒太长了)。我们在枚举的时候,就不从1开始了,而是从这个指针的下一位开始。这是最优性剪枝。
但是需要注意,这个指针需要在这条边建完之后,需要清空。
这个优化显然是基于木棒长度的。如果我们sort一下,让大的在前,这个优化似乎可以派出最大用场。
AC辣!完结撒花。
代码如下。(头文件自己去找,poj不能用bits)
//头文件
using namespace std;
int T,n,a[100],sum,subsum,pos;
int vis[100];
bool dfs(int u,int sum,int pn){
if(sum>=subsum*3){
return 1;
}
for(int i=pn+1;i<=n;++i){
if(!vis[i]){
if((a[i]+sum>subsum&&sum<subsum)||(a[i]+sum>subsum*2&&sum<subsum*2)||(a[i]+sum>subsum*3&&sum<subsum*3))
continue;
if(u+1==n)
return 1;
vis[i]=1;
if((sum+a[i])%subsum==0){
if(dfs(u+1,sum+a[i],0))
return 1;
}
else{
if(dfs(u+1,sum+a[i],i))
return 1;
}
vis[i]=0;
}
}
return 0;
}
bool cmp(int a,int b){
return a>b;
}
signed main(){
cin>>T;
while(T--){
cin>>n;
memset(vis,0,sizeof(vis));
sum=subsum=pos=0;
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
sum+=a[i];
}
if(sum%4!=0){
puts("no");
continue;
}
subsum=sum/4;
sort(a+1,a+n+1,cmp);
if(a[1]>subsum){
puts("no");
continue;
}
vis[1]=1;
if(dfs(1,a[1],1))
puts("yes");
else
puts("no");
}
}