洛谷P1284 三角形牧场 题解

题目链接：P1284 三角形牧场

题意：和所有人一样，奶牛喜欢变化。它们正在设想新造型的牧场。奶牛建筑师 Hei 想建造围有漂亮白色栅栏的三角形牧场。她拥有 $n$ 块木板，每块的长度 $l_i$ 都是整数，她想用所有的木板围成一个三角形使得牧场面积最大。

请帮助 Hei 小姐构造这样的牧场，并计算出这个最大牧场的面积。

显然我们可以枚举两条边的长度，然后用总和减去这两条边的长度就是第三条边的长度

设 $dp[k][i][j]$ 表示只考虑前 $k$ 个木板是否可以形成 $(i,j,S-i-j)$ 的划分

则有

$$dp[k][i][j]=dp[k-1][i][j]\mid dp[k-1][i-a[k]][j]\mid dp[k-1][i][j-a[k]]$$

其中 $\mid$ 表示二进制的或

然后滚动数组一下就完了

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()

int n,sum;
int a[55],dp[1615][1615];
int ck(int a,int b,int c)
{
    return a+b>c&&a+c>b&&b+c>a;
}
double sq(int a,int b,int c)
{
    double p=(a+b+c)*1.0/2;
    return sqrt(p*(p-a)*(p-b)*(p-c));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cout << fixed << setprecision(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    dp[0][0]=1;
    for(int i=1; i<=n; i++)
        cin >> a[i],sum+=a[i];
    for(int k=1; k<=n; k++)
        for(int i=sum/2; i>=0; i--)
            for(int j=sum/2; j>=0; j--)
            {
                if(i>=a[k])dp[i][j]|=dp[i-a[k]][j];
                if(j>=a[k])dp[i][j]|=dp[i][j-a[k]];
            }
    double res=-1;
    for(int i=sum/2; i>=1; i--)
        for(int j=sum/2; j>=1; j--)
            if(dp[i][j]&&ck(i,j,sum-i-j))
                res=fmax(res,sq(i,j,sum-i-j));
    if(res<0)cout << -1 << endl;
    else cout << (int)(res*100) << endl;
    return 0;
}