HDU 5135：狀態壓縮 DP 組合三角形最大面積和

代碼實現

#include <bits/stdc++.h>
using namespace std;

struct Tri { int mask; double area; };

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n;
    while (cin >> n, n) {
        vector len(n);
        for (int &x : len) cin >> x;
        vector tris;
        for (int i = 0; i < n; ++i)
            for (int j = i+1; j < n; ++j)
                for (int k = j+1; k < n; ++k) {
                    int a=len[i], b=len[j], c=len[k];
                    if (a+b>c && a+c>b && b+c>a) {
                        double p = (a+b+c)/2.0;
                        double s = sqrt(p*(p-a)*(p-b)*(p-c));
                        tris.push_back({(1< dp(ALL, 0);
        double ans = 0;
        for (int mask = 0; mask < ALL; ++mask) {
            ans = max(ans, dp[mask]);
            for (auto &t : tris) {
                if ((mask & t.mask) == 0) {
                    int nmask = mask | t.mask;
                    dp[nmask] = max(dp[nmask], dp[mask] + t.area);
                }
            }
        }
        cout << fixed << setprecision(2) << ans << '\n';
    }
    return 0;
}

複雜度

• 三元組枚舉：O(n³)，n ≤ 12 → 220 次。
• DP 狀態：2ⁿ ≤ 4096，每狀態遍歷所有三角形（≤220），總操作 < 10⁶。
• 時間、空間均極小。

關鍵點

• 海倫公式計算面積，double 精度足夠。
• 輸出保留兩位小數 fixed << setprecision(2)。
• 狀態壓縮 DP 是小規模組合優化問題的標準工具。