自动搬运

查看原文

来自洛谷，原作者为

	Cxs3 这个家伙很懒，什么也不想留下

搬运于2025-08-24 21:23:20，当前版本为作者最后更新于2019-09-10 12:28:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接：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$要倒过来循环。这个不难理解，自己思考一下就知道原因了。
$f[0][0]$初始化为$1$。

最后，枚举$i$和$j$，判断能否构成三角形，若可以，用海伦公式求面积，更新答案。
最后的最后，提醒一下求面积的函数里所有变量都要开$double$或$float$，否则只有$\text{45}$分。。。别问我怎么知道的。。。

代码实现

#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;
}