题解 P1284 【三角形牧场】
Ireliaღ
2019-06-01 12:10:25
记忆化搜索，枚举每一条线往哪条边上放就行，注意用`float`卡一下空间。
```cpp
// 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`自动使用科学计数法，所以还得保整一下
```cpp
// 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;
}
```