poj 1948 Triangular Pastures

本文主要是介绍poj 1948 Triangular Pastures，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一个很经典的背包变形，已知三角形的周长，和组成三角形的所有木棍的长度，要求用所有的木棍围成的三角形的面积最大。三角形只要确定两条边就够了，因为周长是知道的。
# include<iostream>
# include<cmath>
# include<stdio.h>
using namespace std;
int f[50];
float g[800][800],ans,a,b,tt;
int main()
{
int i,j,n,k,x,sum,t,ma;
while (cin>>n)
{ 
sum=0;
for (i=1;i<=n;i++)
{
cin>>f[i];
sum+=f[i];
}
memset(g,-1,sizeof(g));
g[0][0]=0;
t=0;
ans=0;
for (i=1;i<=n;i++)
{
t+=f[i];
if (t<sum/2) ma=t;
else
ma=sum/2; 
for (j=ma-1;j>=0;j--)
for (k=ma-1;k>=0;k--)
if (g[j][k]>=0)
{ 
g[f[i]+j][k]=0;
g[j][f[i]+k]=0;
if (f[i]+j<sum/2)
{ 
tt=float(sum)/2;   
if ( ((f[i]+j+k)*2>sum ) && (abs(f[i]+j-k)<sum-f[i]-j-k) )
{
g[j+f[i]][k]=sqrt(tt*(tt-j-f[i])*(tt-k)*(j+f[i]+k-tt));
}
}
if (f[i]+k<sum/2)
{
if ( ((f[i]+j+k)*2>sum ) && (abs(f[i]+k-j)<sum-f[i]-j-k))
g[j][k+f[i]]=sqrt(tt*(tt-j)*(tt-k-f[i])*(j+f[i]+k-tt));
}
if (g[f[i]+j][k]>ans) ans=g[f[i]+j][k]; //a=f[i]+j; b=k;}
if (g[j][f[i]+k]>ans) ans=g[j][f[i]+k]; //a=j; b=f[i]+k;}
}
}
if (ans>0) 
cout<<int(ans*100)<<endl;
else
cout<<-1<<endl;  //cout<<a<<" "<<b<<endl;
}
return 0;
}

 

这篇关于poj 1948 Triangular Pastures的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---