P1284 三角形牧场
Cxs3
·
·
题解
题目链接：https://www.luogu.org/problem/P1284
题目分析
做这道题首先要知道 已知三角形三边长求面积的公式：海伦公式。
接下来就是设状态。背包的题目难就难在这一步，设好状态后方程是很容易写的。
用f[a][b][c]（布尔型）表示三边长为a,b,c的三角形能否围成。但是，三角形的边长的最大值=40*40/2=800，800*800*800显然太大，不可行。
怎么降空间呢？观察题目可以发现，所有n个木板都是要用的，即三角形的周长不变，如果知道了a,b，那么第三边c也知道了。
因此，我们可以用f[k][i][j]表示用前k个木板能否围成两边长为i,j的三角形。
转移时分三种情况：
- 把第k个木板放在i这条边中：
那就要用前k-1个木板围成i-a[k]和j的三角形，即f[k-1][i-a[k]][j]。
- 把第k个木板放在j这条边中：f[k-1][i][j-a[k]]。
- 把第k个木板放在第三条边中：f[k-1][i][j]。
得到动态转移方程：
f[k][i][j]=f[k-1][i-a[k]][j] || f[k-1][i][j-a[k]] || f[k-1][i][j];
观察方程，发现了么？转移时只跟f[k-1][ \ ][ \ ]这层的数据有关，所以我们完全可以去掉第一维，用原数组里的数据更新当前值f[i][j]。
需要注意的是，i,j要倒过来循环。这个不难理解，自己思考一下就知道原因了。
最后，枚举$i$和$j$，判断能否构成三角形，若可以，用海伦公式求面积，更新答案。
最后的最后，提醒一下求面积的函数里所有变量都要开$double$或$float$，否则只有$\text{45}$分。。。别问我怎么知道的。。。
## 代码实现
```cpp
#include<bits/stdc++.h>
const int N=50;
const int L=800+10;
using namespace std;
int n,a[N],sum;
double ans;
bool f[L][L];
bool check(int x,int y,int z)
{
if(x+y>z&&x+z>y&&y+z>x) return 1;
return 0;
}
double work(double x,double y,double z)
{
double p=(x+y+z)/2;
return sqrt(p*(p-x)*(p-y)*(p-z));
}
int main()
{
int i,j,k;
cin>>n;
for(i=1;i<=n;i++){cin>>a[i]; sum+=a[i];}//用sum记录周长
f[0][0]=1;
for(k=1;k<=n;k++)
for(i=sum/2;i>=0;i--)//从周长的一半开始循环
for(j=sum/2;j>=0;j--)
{
if(i-a[k]>=0&&f[i-a[k]][j]) f[i][j]=1;
if(j-a[k]>=0&&f[i][j-a[k]]) f[i][j]=1;
//if(f[i][j]) f[i][j]=1;
//这句可以省略
}
ans=-1;
for(i=sum/2;i>0;i--)
for(j=sum/2;j>0;j--)
{
if(!f[i][j]) continue;
if(!check(i,j,sum-i-j)) continue;//判断能否构成三角形
ans=max(ans,work(i,j,sum-i-j));//更新答案
}
if(ans!=-1) cout<<(long long)(ans*100)<<endl;
else cout<<ans<<endl;
return 0;
}
```