louisfghbvc的部落格

題目說明 :

給你一些棍子的長度，請你算出這些棍子是否可以連成一個正方形。正方形的一個邊可以包含許多棍子。

輸入說明 :

輸入一列數列，第一個整數為 n （ 4 <= n <= 20 ），代表棍子的數目。接下來的 n 個整數分別代表這 M 根棍子的長度，每支棍子的長度介於 1 到 1000 之間。

輸出說明 :

如果這些棍子可以連成一個正方形，輸出 yes 。否則輸出 no 。

思路:

其實也可以不用剪枝, 因為測資不強

1.邊長是否整除4

2.只要做到3邊就可以了(因為前提1如果整除4, 代表做完3邊,第4邊一定可以等於邊長)

3.回溯法，從大的開始做, 預處理要先排序, 算出邊長, 然後開始做dfs 如果用過那個棍子記得要標記拜訪過

程式碼:

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
int arr[25], sum, side, n;
bool vis[25];
bool dfs(int cnt, int i, int len){
    if(cnt == 3){
        return true;
    }
    int tmp = len;
    for(; i < n; i++){
        if(!vis[i]){
            vis[i] = true;
            tmp += arr[i];
            if(tmp == side){
                if(dfs(cnt + 1, 0, 0))
                    return true;
            }
            else if(tmp < side){
                if(dfs(cnt, i + 1, len + arr[i]))
                    return true;
            }
            tmp -= arr[i];
            vis[i] = false;
        }
    }
    return false;
}
int main()
{
    while(cin >> n){
        sum = 0;
        for(int i = 0; i < n; ++i){
            cin >> arr[i];
            sum += arr[i];
        }

        side = sum / 4;
        sort(arr, arr + n, greater<int>());
        memset(vis, 0, sizeof vis);

        if(sum % 4)
            cout << "no\n";
        else{
            if(dfs(0, 0, 0))
                cout << "yes\n";
            else
                cout << "no\n";
        }
    }
    return 0;
}
/**
8 1 7 2 6 4 4 3 5
  7 6 5 4 4 3 2 1
**/