题目描述:
给最多40根木棍,每根长度不超过40,
要用完所有的木棍构成面积最大的三角形,
求出最大的面积。
算法核心
二维01背包
使用到海伦公式:
已知三角形的三边长度a,b,c,求面积
S=√[p(p-a)(p-b)(p-c)]
而公式里的p为半周长:
p=(a+b+c)/2
分析:
用dp[i][j][k]表示到第i根木棒能否摆出边长分别为j,k的三角形
易得
dp[i][j][k] = dp[i-1][j-x[i]][k]|dp[i-1][j][k-x[i]]|dp[i-1][j][k];
简单的
空间压缩,化为二维dp,注意:这里每根木棒只能使用一次,
是01背包,要倒着扫(刚开始错在这里了。。。)
Answer
#include<stdio.h>
#include<string.h>
#include<math.h>
constint N =801;
bool dp[N][N];//dp[i][j]表示取两边分别为i,j可达
int x[N];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int i,j,k;
int sum =0;
for(i=0;i<n;i++)
{
scanf("%d",&x[i]);
sum+=x[i];
}
memset(dp,false,sizeof(dp));
dp[0][0]=true;
int half = sum>>1;
for(i=0;i<n;i++)
for(j=half;j>=0;j--)
for(k=j;k>=0;k--)
{
if(x[i]<=j)
dp[j][k]|=dp[j-x[i]][k];
if(k>=x[i])
dp[j][k]|=dp[j][k-x[i]];
}
double ha = sum/2.0;
double ans =-1;
for(i=0;i<half;i++)
for(j=0;j<=i;j++)
{
if(dp[i][j])
{
k=sum-i-j;
if(i+j>k&&i+k>j&&k+j>i)
{
double temp = ha*(ha-i)*(ha-j)*(ha-k);
if(temp>ans)ans=temp;
}
}
}
intout;
if(ans<0)out=-1;
else
out= (int)(sqrt(ans)*100);
printf("%d\n",out);
}
return0;
}