POJ2362 SOL

2020-03-14 00:59:43


题意:

给你4-20根小木棍,你需要尝试用这些木棍拼接成一个正方形,要求不能多用/少用/折断。多组数据。

这似乎是一道很经典的DFS+剪枝的题目?

首先我们统计sum,看看是不是4的倍数。(这个特判是小学生特判?)

我们直接DFS。递归终点为所有边全部用完,并且递归过程中不能有一根木棒横跨两边。

1

上图中彩色的线段表示小木棍,黑色长线段表示正方形周长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");
    }
}