ZeroJudge D375: Square

同題：UVa 10364 – Square

給你一些棍子的長度，請你算出這些棍子是否可以連成一個正方形 (端點對端點，且棍子不可折斷)。

範例測資

範例輸入範例輸出
輸入的第一列有一個整數 N，代表以下有幾組測試資料。每組測試資料一列，第一個整數為 M (4 <= M <= 20)，代表棍子的數目，接下來的 M 個整數分別代表這 M 根棍子的長度。每支棍子的長度介於 1 到 10000 之間。對每一組測試資料，如果這些棍子可以連成一個正方形，輸出「yes」，否則輸出「no」。
5
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5
8 1 7 2 6 4 4 3 9
8 1 7 2 6 4 4 3 13		yes
no
yes
yes
no
ZeroJudge D375 範例測資

解題思路

因為要用上所有棍子，所以如果所有棍子的總和不是 4 的倍數，那就不可能變成正方形，或是最長的棍子大於總和除以 4，這樣也不能變成正方形。

使用 DFS 的方式去判斷每一種可能。

範例程式碼－ZeroJudge D375: Square

#include <iostream>
#include <algorithm>
using namespace std;

bool ok = false;
int MAP[50000] = {}, stick[50000] = {}, N;

void DFS(const int length, const int finish, const int add, const int start) {
    if (finish == 3 || ok) {
        ok = true;
        return;
    }
    if (add == length) {
        DFS(length, finish+1, 0, 0);
        return;
    }
    for (int i = start; i<N; i++) {
        if (MAP[i] == 0 && add+stick[i] <= length) {
            MAP[i] = 1;
            DFS(length, finish, add+stick[i], i+1);
            MAP[i] = 0;
        }
        else if (stick[i]+add > length) return;
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    for (int i = 0; i<T; i++) {
        int sum = 0, max = -999;
        cin >> N;
        ok = false;
        for (int j = 0; j<N; j++) {
            MAP[j] = 0;
        }
        for (int j = 0; j<N; j++) {
            cin >> stick[j];
            sum += stick[j];
            if (stick[j] > max) max = stick[j];
        }
        if (sum % 4 != 0 || max > sum / 4) {
            cout << "no\n";
            continue;
        }
        sort(stick, stick+N);
        DFS(sum / 4, 0, 0, 0);
        if (ok) cout << "yes\n";
        else cout << "no\n";

    }
}

//ZeroJudge D375
//Dr. SeanXD
標籤

相關文章

發佈留言