POJ1948Triangular Pastures（DP）

POJ1948http://poj.org/problem?id=1948

题目大意就是说给你n个木棍让你用它们摆成一个三角形  使得这个三角形的面积最大。

这个题我之前想的时候一直纠结怎么通过之前的三角形面积推导出加上一条木棍后的面积，结果一直没有想明白，而且总周长达到了1600，他的平方肯定会超时才对。后来看了网上的题解才明白其实DP求出来的并不是这些三角行是面积，而是求出通过这n个木棍可以构成哪些边长组合的三角形，最后再一一比较这些三角形的面积。

至于判断三角形，由于最长的边也不可能超过三角形周长的一半，也就是800，所以最后的结果就是800*800自然不会超时。

#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a < b ? a : b)
#define mem0(a) memset(a,0,sizeof(a))

typedef long long LL;
const double eps = 1e-12;
const int MAXN = 1005;
const int MAXM = 5005;

bool DP[880][880];
int len[42], tot, N;

bool Judge(int a,int b,int c)
{
    if(a+b>c && a+c>b && b+c>a) return true;
    return false;
}

double area(int a, int b, int c)
{
    double p = (double)(a+b+c)/2.0;
    return sqrt(p*(p-a)*(p-b)*(p-c));
}

int main()
{
    while(~scanf("%d", &N))
    {
        tot = 0; mem0(DP);
        for(int i=0;i<N;i++)
        {
            scanf("%d", &len[i]);
            tot += len[i];
        }
        int half = tot/2;
        DP[0][0] = 1;
        for(int i=0;i<N;i++)
        {
            for(int j=half;j>=0;j--)
            {
                for(int k=half;k>=0;k--)
                {
                    if((j>=len[i]&&DP[j-len[i]][k]) || (k>=len[i]&&DP[j][k-len[i]]))
                    {
                        DP[j][k] = 1;
                    }
                }
            }
        }
        double ans = -1;
        for(int i=0;i<=half;i++)
        {
            for(int j=0;j<=half;j++)
            {
                if(DP[i][j] && Judge(i,j,tot-i-j))
                {
                    ans = max(ans, 100*area(i,j,tot-i-j));
                }
            }
        }
        printf("%d
", (int)ans);
    }
    return 0;
}