题解
1.看到数据范围很小,所以我们可以穷举
如何穷举呢?
三个方向的背包dp,令 \(dp[i][j][k]\) 来表示 三边长度为 \(i,j,k\) 时能否达到,然后最外面一维是所用的木板
由于她想用所有的木板 所以 \(k=total-i-j\) ,所以可以变成两维
注意这里的背包dp要倒着来,不然继承的状态是刚刚才刷新的状态
code
#include<bits/stdc++.h>
using namespace std;
int line[50];
int wh[1605][1605]={0};
#define db double
double area(db i,db j,db k)//方便计算
{
double p=(i+j+k)/2;
return sqrt(p*(p-i)*(p-j)*(p-k));
}
int main()
{
ios::sync_with_stdio(false);
int n,total=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>line[i];
total+=line[i];
}
wh[0][0]=1;
for(int k=1;k<=n;k++)
{
for(int i=total;i>=0;i--)
{
for(int j=total;j>=0;j--)//不管三角形的限制,直接算就完了
{
if(i>=line[k]) wh[i][j]|=wh[i-line[k]][j];
if(j>=line[k]) wh[i][j]|=wh[i][j-line[k]];
}
}
}
double ans=0;
int flag=0;
for(int i=1;i<=total;i++)
{
for(int j=1;j<=total;j++)
{
int k=total-i-j;
if(i+j>k&&k+j>i&&k+i>j&&wh[i][j])//在这里再考虑是否是三角形
{
ans=max(ans,area((db)i,(db)j,(db)k));
flag=1;
}
}
}
if(!flag) puts("-1");
else printf("%.0lf",floor(ans*100));
return 0;
}
标签:int,db,牧场,wh,P1284,ans,三角形,total,line
From: https://www.cnblogs.com/pure4knowledge/p/18102314