POJ2362 Square 搜索

題目描述

給n個木棒問能否拼成正方形(不許彎折)

Sample Input
3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5

Sample Output
yes
no
yes

解題思路

1.總長度必須是4的倍數 2.最長邊不能大於邊長 3.滿足1 2後找到了3條邊就可以了

將所有的木棒遞減排列從頭開始搜索，這樣dfs深度可能小一點。dfs順序是拓撲序，就是說每次搜一個木棒時只需要向它右邊的搜索就可以了。代碼如下

#include 
#include 
#include 
using namespace std;
const int maxn = 22;
int vis[maxn];
int s[maxn];
int n,sum;
bool cmp(int x,int y)
{
    return x>y;
}

bool dfs(int _sum,int start,int kase)//_sum:當前已經組成了多少長度  start:從哪裡開始找   kase:已經拼成了幾個
{
    if(kase == 3) return true;
    if(_sum == sum/4) if(dfs(0,1,kase+1)) return true;
    for(int i = start; i <= n ; i ++) {
        if(!vis[i]) {
            vis[i] = 1;
            if(dfs(_sum+s[i],i+1,kase)) return true;
            vis[i] = 0;
        }
    }
    return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--) {
        memset(vis,0,sizeof vis);
        sum = 0;
        scanf("%d",&n);
        for(int i = 1 ; i <= n ; i ++) {
            scanf("%d",&s[i]);
            sum += s[i];
        }
        sort(s+1,s+n+1,cmp);
        if(sum%4 || s[n]>sum/4) {
            printf("no\n");
            continue;
        }
        if(dfs(0,0,0)) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}