POJ 1948 DP

题意：给你n个木棍（n<=40）每个木棍长度<=40，问用上所有的木棍拼成的三角形的面积的最大值，并输出面积*100的值（不四舍五入） 如果没有解，输出-1。

思路：

背包判断可达性。

f[j][k]表示能拼成一个长度为j的边，一个长度为k的边。

所以 if(f[j][k]&&j+a[i]<=800&&k+a[i]<=800)

f[j+a[i]][k]=f[j][k+a[i]]=1;

因为三角形的周长是一定的，可以求出剩下那条边的长度。

用余弦定理可得出cosα。sina=sqrt(1-cosa*cosα)然后S=0.5*b*c*sinα

跟最优解比较一下就好咯

// by SiriusRen

#include <cmath>

#include <cstdio>

#include <algorithm>

using namespace std;

int n,a[50],sum=0;

bool f[805][805];

double ans=0;

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

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

        sum+=a[i];

    }

    f[0][0]=1;

    for(int i=1;i<=n;i++)

        for(int j=800;j>=0;j--)

            for(int k=800;k>=0;k--)

                if(f[j][k]&&j+a[i]<=800&&k+a[i]<=800)

                    f[j+a[i]][k]=f[j][k+a[i]]=1;

    for(int i=1;i<=800;i++)

        for(int j=1;j<=800;j++)

            if(f[i][j]){

                int A=sum-i-j;

                if(i+j<=A||i+A<=j||j+A<=i)continue;

                double COSA=(1.0*i*i+j*j-A*A)/(2.0*i*j);

                double SINA=sqrt(1-COSA*COSA);

                ans=max(ans,0.5*i*j*SINA);

            }

    n=floor(ans*100);

    if(n)printf("%d",n);

    else puts("-1");

}