洛谷 P1284 三角形牧场

url: https://www.luogu.com.cn/problem/P1284

tag:
动态规划，贪心，背包DP

思路：
用 f[k][i][j] 来表示前k块木板能否组成三角形。所以状态转移方程为：
f[k][i][j] = f[k - 1][i - a[k]][j] || f[k - 1][i][j - a[k]] || f[k][i][j]
因为转移时只跟 f[k - 1][][] 层的数据有关，所以可以用类似01背包问题的方式来简化掉这一维。初始化 f[0][0] = 1 之后对于每一个可能的结果判断是否为合法三角形，然后计算面积更新最大值即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 50;
int n, sum;
int a[N];
bool f[N * N][N * N];
long long ans;
bool check(int a, int b, int c)
{
    return a + b > c && a + c > b && b + c > a;
}
double resolue(int a, int b, int c)
{
    double p = (a * 1.0 + b + c) / 2;
    return sqrt(p * (p - a) * (p - b) * (p - c));
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        sum += a[i];
    }
    f[0][0] = 1;
    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] >= 0 && f[i - a[k]][j]) f[i][j] = 1;
                if (j - a[k] >= 0 && f[i][j - a[k]]) f[i][j] = 1;
            }
    double res = -1;
    for (int i = sum / 2; i > 0; i --)
        for (int j = sum / 2; j > 0; j --)
        {
            if (!f[i][j]) continue;
            if (!check(i, j, sum - i - j)) continue;
            res = max(res, resolue(i, j, sum - i - j));
        }
    if (res == -1) cout << -1 << endl;
    else cout << (long long)(res * 100) << endl;
    return 0;
}