# Irelia

### 题解 P1284 【三角形牧场】

posted on 2019-06-01 12:10:25 | under 题解 |

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

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