题解：P12767 [POI 2018 R3] 围栏 Fence
Register_int
·
·
题解
有点厉害的题。也可能是我没见过这类套路。
预处理三角形内点权和与 dp 转移都是 $\mathcal{O}(n^3)$ 的，需要进一步优化。
### Part I：三角形内数点
假设我们考察的是 $i<j$ 与原点构成的三角形。对于一个点 $k$，他必须要满足 $i<k<j$ 才可能被计入贡献。
这看着怎么这么像一维限制，那是不是得想办法凑出第二维？三角形数点我不会，但是二维数点我会啊！
发现 $i<k<j$ 本质上是限制了夹角的范围。考虑用两个角就能夹出来一个三角形，于是我们将 $i+1\sim n$ 的点以 $i$ 为中心极角排序，得到每个点的排名 $rk$，那么 $k$ 能造成贡献的的条件为 $rk_k<rk_j$。这样就是二维数点了，上树状数组即可，时间复杂度 $\mathcal{O}(n^2\log n)$。实测只做这个优化也[跑的飞快](https://www.luogu.com.cn/record/258616531)。
### Part II：dp 转移
朴素的转移就是设 $dp_{i,j}$ 表示上一条边为 $i\to j$ 时的答案，转移需要枚举上一个点 $k$ 并判断是否能构成凸包，然后 $dp_{i,j}\gets dp_{k,i}+w(i,j)$。
也就是我们要做的是快速求 $\max_k dp_{k,i}$。注意到极角排序后 $k$ 构成一段前缀，前缀和优化 dp 即可。时间复杂度 $\mathcal{O}(n^2\log n)$。
于是我们在 $\mathcal{O}(n^3\log n)$ 的复杂度下解决了这个问题。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e2 + 10;
typedef struct Point {
ll x, y;
Point(ll x = 0, ll y = 0) : x(x), y(y) {}
Point operator - (const Point &rhs) const { return Point(x - rhs.x, y - rhs.y); }
ll operator ^ (const Point &rhs) const { return x * rhs.y - y * rhs.x; }
} Vector;
int n, m; pair<Point, ll> a[MAXN], b[MAXN];
ll w[MAXN][MAXN], dp[MAXN][MAXN], ans = -1e18;
int id[MAXN], rk[MAXN]; ll c[MAXN];
inline void add(int k, ll x) { for (int i = k; i <= m; i += i & -i) c[i] += x; }
inline ll ask(int k) { ll res = 0; for (int i = k; i; i &= i - 1) res += c[i]; return res; }
inline
void solve() {
sort(b + 1, b + m + 1, [](auto x, auto y) -> bool {
if (!x.first.x && !x.first.y) return 1;
return (x.first ^ y.first) > 0;
});
for (int i = 2; i < m; i++) {
for (int j = i + 1; j <= m; j++) id[j] = j;
sort(id + i + 1, id + m + 1, [=](auto x, auto y) {
return (b[x].first - b[i].first ^ b[y].first - b[i].first) < 0;
});
for (int j = i + 1; j <= m; j++) rk[id[j]] = j;
for (int j = 1; j <= m; j++) c[j] = 0;
for (int j = i + 1; j <= m; j++) w[i][j] = b[i].second + ask(rk[j]), add(rk[j], b[j].second);
}
memset(dp, 0xc0, sizeof dp);
for (int i = 2; i <= m; i++) dp[1][i] = b[1].second;
for (int i = 2; i < m; i++) {
vector<int> tmp;
for (int j = 1; j <= m; j++) if (j != i) tmp.emplace_back(j);
sort(tmp.begin(), tmp.end(), [=](int x, int y) -> bool {
Vector tx = x < i ? b[i].first - b[x].first : b[x].first - b[i].first;
Vector ty = y < i ? b[i].first - b[y].first : b[y].first - b[i].first;
return (tx ^ ty) > 0;
});
ll val = -1e18;
for (int j : tmp) {
if (j > i) dp[i][j] = max(dp[i][j], val + w[i][j]);
else val = max(val, dp[j][i]);
}
}
for (int i = 2; i <= m; i++) {
for (int j = i + 1; j <= m; j++) ans = max(ans, dp[i][j] + b[j].second);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld%lld%lld", &a[i].first.x, &a[i].first.y, &a[i].second);
for (int i = 1; i <= n; i++) {
m = 0;
for (int j = 1; j <= n; j++) {
if (a[j].first.y >= a[i].first.y) {
b[++m] = make_pair(a[j].first - a[i].first, a[j].second);
}
}
solve();
}
printf("%lld", ans);
}
```