POJ 1948 Triangular Pastures（背包，经典）

题目意思：
给出n条边，然后用这n条边组成一个三角形，求该该三角形的
最大面积。

本题要点：
1、转态表示：
dp[i][j] 表示三角形第一条边是i， 第二条边是j的 三角形是否存在。
（i >= j）
3、 转态转移：
if(dp[i][j]) // 扫描第k条边的时候
{
dp[i + a[k]][j] = dp[i][j + a[k]] = 1;
}
4、 三条边能组成三角形的充要条件是：
任意两条边的和大于第三条边。假设所有线段的总和是 s，
这些线段组成的三角形的最长边是 m = s / 2 - ((s & 1) == 0);
5、 扫描顺序：
从大到小扫描， 保持 i >= j
5、海伦公式 s = sqrt(p * (p - x) * (p - y) * (p - z));
其中 p = (x + y + z) / 2.0;

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
const int MaxN = 1610;
int dp[MaxN][MaxN];
int n, s;
int a[MaxN];int calc_s(double x, double y, double z)
{
    	double p = (x + y + z) / 2.0;return sqrt(p * (p - x) * (p - y) * (p - z)) * 100;
}void solve()
{
    // m表示一条边可能的最大长度int m = s / 2 - ((s & 1) == 0), ans = -1;for(int i = 0; i <= m; ++i)for(int j = 0; j <= i; ++j){
    dp[i][j] = 0;}dp[0][0] = 1;for(int k = 1; k <= n; ++k){
    for(int i = m; i >= 0; --i){
    for(int j = i; j >= 0; --j){
    if(dp[i][j]){
    dp[i + a[k]][j] = dp[i][j + a[k]] = 1;	}}}}for(int i = m; i >= 0; --i)for(int j = i; j >= 0; --j){
    if(dp[i][j]){
    ans = max(ans, calc_s(i, j, s - i - j));//如果 边长 i，j能够成三角形的两边，第三边肯定是剩下的所有长度 s - i - j}}printf("%d\n", ans);
}int main()
{
    s = 0;scanf("%d", &n);for(int i = 1; i <= n; ++i){
    scanf("%d", &a[i]);s += a[i];}solve();return 0;
}/* 5 1 1 3 3 4 *//* 692 */