题解：UVA10364 Square

__DAN__ · 2024-12-17 21:29:52 · 题解

题目传送门

正解(搜索剪枝)

当总长度不是四的倍数时不可行。

接着将长度和除以 4 ，得到每条边的长度 l 。用一个变量 flag 代表当前是否有可行方案。之后暴力搜索，并定义四个变量 a,b,c,d ，分别代表四条边已有的长度。若木棒加上此边的长度超过了 l ,则跳过（剪枝操作）。本条边加上木棍长度，进行下一步搜索，并回溯。若flag=1，（已有可行方案）则可以直接跳过以上操作。当木棍遍历结束，可直接判断 a=b 且 b=c 且 c=d ，若等于则flag=1。最后输出。

代码展示

#include<bits/stdc++.h>
using namespace std;
int T,n,s;
int a[25],b[5];
int fl=0;
void dfs(int i){
    if(i==n+1){
        if(b[1]==b[2]&&b[2]==b[3]&&b[3]==b[4]) fl=1;
        return;
    }
    for(int j=1;j<=4;j++){
        if(b[j]+a[i]>s) continue;
        if(fl==0){
            b[j]+=a[i];
            dfs(i+1);
            b[j]-=a[i];
        }
        else break;
    }
}
int main(){
    cin>>T;
    while(T--){
        memset(b,0,sizeof(b));
        fl=0;
        s=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            s+=a[i];
        }
        if(s%4!=0){
            cout<<"no"<<"\n"; 
            continue;   
        }
        s/=4;
        dfs(1);
        if(fl==1) cout<<"yes"<<"\n";
        else cout<<"no"<<"\n";
    }
    return 0;
}