POJ 1948 Triangular Pastures

USACO 2002 February의 한 문제입니다.
많은 단독 라인을 하나의 삼각형으로 재조합하여 삼각형의 면적을 가장 크게 한다는 뜻이다.모든 세그먼트는 반드시 사용해야 한다.
해법은 동적 기획이다.
가방의 사고방식으로 dp[i][j]는 1이고 이 라인에서 한 변의 길이는 i이고 다른 한 변은 j의 삼각형을 구성할 수 있음을 나타낸다.0이면 사용할 수 없음을 나타냅니다.
둘레가 일정하기 때문에 dp[i][j]는 삼각형의 변이 각각 i, j, c-i-j라는 것을 나타낸다. 헬렌 공식을 통해 면적을 계산할 수 있다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
bool check[1000][1000];
double check_and_calc_the_area(int a,int b,int c,double &t)
{
    double q;
    if (a+b <= c || a+c <= b || b+c <= a)
        return false;
    q=(a+b+c)/2.0;
    t=sqrt(q*(q-a)*(q-b)*(q-c));
    t*=100;
    return true;
}
int main()
{
    int hc,i,j,k,c,l[50],n,ans;
    double t;
    scanf("%d",&n);
    c=0;
    for (i=0; i<n; i++)
    {
        scanf("%d",l+i);
        c+=l[i];
    }
    hc=c>>1;
    memset(check,false,sizeof(check));
    check[0][0]=true;
    for (i=0; i<n; i++)
    {
        for (j=hc; j>=0; j--)
        {
            for (k=hc; k>=0; k--)
            {
                if (j >= l[i])
                {
                    if (check[j-l[i]][k])
                        check[j][k]=true;
                }
                if (k >= l[i])
                {
                    if (check[j][k-l[i]])
                        check[j][k]=true;
                }
            }
        }
    }
    ans=0;
    for (i=1; i<=hc; i++)
    {
        for (j=1; j<=hc; j++)
        {
            if (check[i][j] == true)
            {
                if (check_and_calc_the_area(i,j,c-i-j,t) == true)
                    ans=(int)t>ans?(int)t:ans;
            }
        }
    }
    printf("%d",ans==0?-1:ans);
}