Untitled
plain_text
a month ago
2.5 kB
1
Indexable
Never
#include <iostream> #include <cstring> #include <cmath> using namespace std; double r[10], x[10], map[10][10], ans; int used[10], rx[10]; // 用於記錄元素是否被使用的陣列 void dfs(int idx, int n) { if (idx == n) { // 若已經遍歷完所有元素 double xs = 0; int i; for (i = 0; i < n; i++) { // 計算最大半徑和 if (r[rx[i]] + x[i] > xs) { xs = r[rx[i]] + x[i]; } } if (ans > xs) { // 更新答案 ans = xs; } return; } int i, j, k, f; double xs; for (i = 0; i < n; i++) { if (!used[i]) { rx[idx] = i; // 紀錄已經選擇的元素的索引 f = 0; xs = r[i]; for (j = idx - 1; j >= 0; j--) { xs = x[j] + 2 * map[i][rx[j]]; for (k = j - 1; k >= 0; k--) { if (xs < 2 * map[i][rx[k]] + x[k]) { break; } } if (k == -1) { f = 1; break; } } if (xs < r[i]) { // 確保新半徑不小於初始半徑 xs = r[i]; } x[idx] = xs; // 紀錄新的半徑 if ((f == 0 && idx != 0) || (xs + r[i] >= ans)) { // 若不滿足條件則跳過 continue; } used[i] = 1; // 標記元素已被使用 dfs(idx + 1, n); // 遞迴進行下一層選擇 used[i] = 0; // 還原元素的使用狀態 //it's called 回溯法 } } } int main() { int n, m, i, j; cin >> n; while (n--) { cin >> m; memset(used, 0, sizeof(used)); ans = 0; // 初始化答案 for (i = 0; i < m; i++) { cin >> r[i]; // 讀取元素的初始半徑 ans += r[i]; // 累加到答案中 } for (i = 0; i < m; i++) { for (j = 0; j < m; j++) { map[i][j] = sqrt(r[i] * r[j]); // 計算距離並存儲在map陣列中 } } ans *= 2; // 初始化答案為最大可能值 dfs(0, m); // 呼叫深度優先搜尋函式進行選擇, 從0開始 cout << fixed; cout.precision(3); cout << ans << endl; // 輸出答案 } return 0; }