记忆化搜索,枚举每一条线往哪条边上放就行,注意用float卡一下空间。

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>

using namespace std;

const int MAXN = 45;
const float EPS = 1e-5;

int n;
int a[MAXN], s[MAXN];
float dp[MAXN][MAXN * MAXN][MAXN * MAXN];
//map<int, map<int, map<int, float> > > dp;

bool Judge(float a, float b, float c) {
    return a + b - c > EPS && a + c - b > EPS && b + c - a > EPS;
}

float Area(float a, float b, float c) {
    if (!Judge(a, b, c)) return -0.010000;
    float m = (a + b + c) / 2.000000;
    return sqrt(m * (m - a) * (m - b) * (m - c));
}

float Dfs(int pos, int l1, int l2) {
    if (dp[pos][l1][l2] < -EPS || dp[pos][l1][l2] > EPS) return dp[pos][l1][l2];
    if (pos == n) {
        int l3 = s[pos - 1] - l1 - l2;
        return dp[pos][l1][l2] = max(Area(l1, l2, l3 + a[pos]), max(Area(l1, l2 + a[pos], l3), Area(l1 + a[pos], l2, l3)));
    }
    return dp[pos][l1][l2] = max(Dfs(pos + 1, l1 + a[pos], l2), max(Dfs(pos + 1, l1, l2 + a[pos]), Dfs(pos + 1, l1, l2)));
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) s[i] = a[i] + s[i - 1];
    cout << floor(Dfs(0, 0, 0) * 100.000000) << endl;
    return 0;
}

你复制粘贴,提交,诶,怎么才45分?果断下载数据点。

标准输出

2927165

我的输出

2.92716 e 6

floor虽然取整了,但是返回的类型还是浮点,位数多cout自动使用科学计数法,所以还得保整一下

// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <map>

using namespace std;

const int MAXN = 45;
const float EPS = 1e-5;

int n;
int a[MAXN], s[MAXN];
float dp[MAXN][MAXN * MAXN][MAXN * MAXN];
//map<int, map<int, map<int, float> > > dp;

bool Judge(float a, float b, float c) {
    return a + b - c > EPS && a + c - b > EPS && b + c - a > EPS;
}

float Area(float a, float b, float c) {
    if (!Judge(a, b, c)) return -0.010000;
    float m = (a + b + c) / 2.000000;
    return sqrt(m * (m - a) * (m - b) * (m - c));
}

float Dfs(int pos, int l1, int l2) {
    if (dp[pos][l1][l2] < -EPS || dp[pos][l1][l2] > EPS) return dp[pos][l1][l2];
    if (pos == n) {
        int l3 = s[pos - 1] - l1 - l2;
        return dp[pos][l1][l2] = max(Area(l1, l2, l3 + a[pos]), max(Area(l1, l2 + a[pos], l3), Area(l1 + a[pos], l2, l3)));
    }
    return dp[pos][l1][l2] = max(Dfs(pos + 1, l1 + a[pos], l2), max(Dfs(pos + 1, l1, l2 + a[pos]), Dfs(pos + 1, l1, l2)));
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) s[i] = a[i] + s[i - 1];
    cout << fixed<< setprecision(0) << floor(Dfs(0, 0, 0) * 100.000000) << endl;
    return 0;
}