POJ 1948 Triangular Pastures

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意:

把很多单独的线段重新组合成一个三角形，使得三角形面积最大(所有的线段都必须用上)。

思路：

三角形的任意一条边的边长不能超过周长的一半，只需要用dp枚举两条边j,k，剩下的一条边长为tot - j - k;判断枚举出的这三条边是否能组成三角形，用海伦公式求出面积

代码：

#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-;

const int MAXN = ;

const int MAXM = ;

bool DP[][];

int len[], 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 = ; mem0(DP);

        for(int i=;i<N;i++)

        {

            scanf("%d", &len[i]);

            tot += len[i];

        }

        int half = tot/;

        DP[][] = ;

        for(int i=;i<N;i++)

        {

            for(int j=half;j>=;j--)

            {

                for(int k=half;k>=;k--)

                {

                    if((j>=len[i]&&DP[j-len[i]][k]) || (k>=len[i]&&DP[j][k-len[i]]))

                    {

                        DP[j][k] = ;

                    }

                }

            }

        }

        double ans = -;

        for(int i=;i<=half;i++)

        {

            for(int j=;j<=half;j++)

            {

                if(DP[i][j] && Judge(i,j,tot-i-j))

                {

                    ans = max(ans, *area(i,j,tot-i-j));

                }

            }

        }

        printf("%d\n", (int)ans);

    }

    return ;

}