Untitled

mail@pastecode.io avatarunknown
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;
}