UVA 10364 - Square
Contents
本題為中山大學高等程式設計課程作業指定題目之四星題。
題目大意
有 n 個棍子，輸出在所有棍子緊密相連的情況下，這 n 個棍子能否組成一個正方形。
輸入範圍
4 <= n <= 20，1 <= 每個棍子長度 <= 10000。
解法
這題基本上就是枚舉每個邊，但直接枚舉的時間複雜度高達 O(4^N)，基本上一定 TLE，注意以下幾點可以避免：
- 先判斷棍子總長度是否為 4 的倍數，不是的話絕對不可能組成正方形。
- 只要符合 1，且找到正方形的其中三個邊，剩下的棍子一定能組成第四個邊。
- 從大的棍子開始找，可以避免很多不必要的遞迴。
基本上做完些事，AC 就差不多到手了，我的程式碼 line 16-17 單純在做 I/O 優化，單純寫這題前在打 Code Jam，一回神已經寫了XD
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
bool dfs(int arr[], int n, int k, int target, int sum, int id) {
if (k == 3) return true;
if (sum == target) return dfs(arr, n, k+1, target, 0, 0);
for(int i=id; i<n; i++) {
if (!arr[i] || sum + arr[i] > target) continue;
int temp = arr[i]; arr[i] = 0;
if (dfs(arr, n, k, target, sum+temp, i+1)) return true;
arr[i] = temp;
}
return false;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--) {
int n, arr[21], sum = 0, maxi = 0;
cin >> n;
for(int i=0; i<n; i++) {
cin >> arr[i];
sum += arr[i];
maxi = max(maxi, arr[i]);
}
if (sum % 4 || maxi > sum / 4) {
cout << "no\n";
continue;
}
sort(arr, arr+n, [](int a, int b) {return a > b;});
cout << (dfs(arr, n, 0, sum / 4, 0, 0) ? "yes" : "no") << endl;
}
return 0;
}