题目链接：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;
}

by hansang:

#include<bits/stdc++.h>
using namespace std;
const int N=45, M=1620;
int a[N], f[2][M][M];
bool pd(int i, int j, int k){
	if(i+j<=k || abs(i-j)>=k) return 0;
	if(i+k<=j || abs(i-k)>=j) return 0;
	if(j+k<=i || abs(k-j)>=i) return 0;
	if((i<=0) || (j<=0) || (k<=0)) return 0;
	return 1;
}
double calc(double i, double j, double k){
	double p=(i+j+k)/2;
	double res=sqrt(p*(p-i)*(p-j)*(p-k))*100.0;
	return res;
}
int main(){
	int n, sum=0; scanf("%d", &n);
	for(int i=1; i<=n; i++){
		scanf("%d", &a[i]);
		sum+=a[i];
	}
	double ans=0;
	memset(f, 0, sizeof(f)); f[0][0][0]=1;
	for(int i=1; i<=n; i++){
		for(int j=0; j<=sum/2; j++){
			for(int k=0; k<=sum/2; k++) if(f[(i-1)&1][j][k]){
				f[i&1][j+a[i]][k]=1;
				f[i&1][j][k+a[i]]=1;
				f[i&1][j][k]=1; 
				
				int t=sum-k-j-a[i];
				if(pd(j+a[i], k, t)) ans=max(ans, calc(j+a[i], k, t));
				if(pd(j, k+a[i], t)) ans=max(ans, calc(j, k+a[i], t));
			}
		}
	}
	printf("%d\n", (!ans)? -1: (int)ans);
	return 0;
}