- 状态:
dp[i][j]表示用i和j的木板能否搭成，不用去管第三块，因为知道了两块的长度与周长，那就可以表示出第三块:c-i-j
- 转移
有点类似于背包
if((j-l[i]>=0&&dp[j-l[i]][k])||(k-l[i]>=0&&dp[j][k-l[i]]))dp[j][k]=1;
因为此状态只可能从没加上这根木板的时候转移过来
- 判断
判断这三块木板能否组成三角形
inline bool check(int a,int b,int c)
{
if(a+b>c&&a+c>b&&b+c>a)return 1;
return 0;
}
check(i,j,c-i-j)
- 计算面积
这里用到了海伦公式
\(S=\sqrt{p*(p-a)*(p-b)*(p-c)}\)
\(p\)为半周长:\((a+b+c)/2\)
具体可以查百度
inline double get(double a,double b,double c)//注意，这里不能定义成整型，否则会WA
{
double p=(a+b+c)/2;
return sqrt(p*(p-a)*(p-b)*(p-c));
}
献上完整代码:
#include<bits/stdc++.h>
using namespace std;
int n,c;
int l[50];
int wood[4];
bool dp[800+10][800+10];
inline double get(double a,double b,double c)//计算面积
{
double p=(a+b+c)/2;
return sqrt(p*(p-a)*(p-b)*(p-c));
}
inline bool check(int a,int b,int c)//能否组成三角形
{
if(a+b>c&&a+c>b&&b+c>a)return 1;
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
cin>>l[i],c+=l[i];
dp[0][0]=1;//初始状态
for(int i=1;i<=n;i++)
{
for(int j=c/2;j>=0;j--)
{
for(int k=c/2;k>=0;k--)
{
if((j-l[i]>=0&&dp[j-l[i]][k])||(k-l[i]>=0&&dp[j][k-l[i]]))dp[j][k]=1;//状态转移
//cout<<dp[j][k]<<" ";
}
//cout<<endl;
}
}
double ans=-1;
for(int i=c/2;i>=1;i--)
{
for(int j=c/2;j>=1;j--)
{
if(dp[i][j]&&check(i,j,c-i-j))ans=max(ans,get(i,j,c-i-j));//找到最大值
}
}
cout<<(int)(ans==-1?-1:ans*100)<<endl;
return 0;
}