POJ 1948 Triangular Pastures：0-1 背包枚舉三角形最大面積

問題轉化

給定若干木棍，選若干根組成三條邊構成三角形，求最大面積。無法構成輸出 -1。
設總長度和為 S，三邊為 a, b, c，則 a + b + c = S。只需確定 a, b，第三邊 c = S - a - b。

DP 狀態設計

dp[i][j] = 能否用部分木棍同時湊出長度 i 和 j 的兩條邊（順序無關）。
初始 dp[0][0] = true。對每根長度 L 的木棍，做 0-1 背包逆序更新：

for i = 800..0:
    for j = 800..0:
        if dp[i][j]:
            if i+L < N: dp[i+L][j] = true
            if j+L < N: dp[i][j+L] = true

枚舉驗證與面積計算

遍歷所有 dp[i][j] == true，設 x = S - i - j，檢查三角形不等式 i+j>x, i+x>j, j+x>i。
面積用海倫公式或底高公式：

double area(int x, int y, int z) {
    double p = (x*x - y*y + z*z) / (2.0 * z);  // 底 z 上的投影
    double h = sqrt(x*x - p*p);                 // 高
    return h * z / 2 * 100;                     // 放大 100 取整
}

維護最大面積整數值輸出。

完整代碼

#include <stdio.h>
#include <string.h>
#include <math.h>
const int N = 805;
int n, s, dp[N][N];

void add(int l) {
    for (int i = 800; i >= 0; i--)
        for (int j = 800; j >= 0; j--)
            if (dp[i][j]) {
                if (i + l < N) dp[i+l][j] = 1;
                if (j + l < N) dp[i][j+l] = 1;
            }
}

void init() {
    s = 0; memset(dp, 0, sizeof(dp)); dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        int l; scanf("%d", &l); s += l; add(l);
    }
}

int area(double x, double y, double z) {
    double p = (x*x - y*y + z*z) / (2*z);
    double h = sqrt(x*x - p*p);
    return (int)(h * z / 2 * 100);
}

void solve() {
    int ans = -1;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (dp[i][j]) {
                int x = s - i - j;
                if (i + j <= x || i + x <= j || j + x <= i) continue;
                ans = max(ans, area(i, j, x));
            }
    printf("%d\n", ans);
}

int main() {
    while (scanf("%d", &n) == 1 && n) { init(); solve(); }
    return 0;
}