我们可以把所有点都对称到主对角线下方。
然后每个点如果想被覆盖都会有一个最小的三角形，我们可以贪心的只留必须选的点。如果把剩下的点按 \(x\) 坐标升序排序，可以发现他们的 \(y\) 坐标也是升序排序的。
记剩余点个数为 \(n\)，显然每个点都选自己的最小三角形最好。但是有可能 \(n>K\)，即我们不得不合并一些连续的最小三角形。可以 \(dp\)，\(f_{i,k}\) 表示覆盖前 \(i\) 个点，用了 \(k\) 个三角形的最少覆盖点。枚举 \(j\)，把 \(j+1\sim i\) 用一个三角形覆盖，转移即可。
\[f_{i,k}={f_{j,k−1}+(x_i−y_j+1+1)}^2 \]注意处理重叠的点，要减去这些点，可以直接记在 \(f_{j,k-1}\) 里。
发现可以斜率优化，\(O(n\times k)\)。
还是过不去，我们考虑 wqs 二分，降维打击！
复杂度 \(O (n \log m)\)
#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
#define inf 0x3f3f3f3f
struct P {
int x, y;
} p[N];
inline bool cmp(P a, P b) {
return a.x == b.x ? a.y > b.y : a.x < b.x;
}
inline ll sqr(ll x) {
return x * x;
}
ll f[N];
int cnt[N], q[N], qh, qt;
inline double slope(int k1, int k2) {
return (f[k2] - f[k1] + sqr(p[k2 + 1].y) - sqr(p[k1 + 1].y)) * 1.0 / (2 * (p[k2 + 1].y - p[k1 + 1].y));
}
inline int solve(int n, ll C) {
qh = 1;
qt = 0;
q[++qt] = 0;
for (int i = 1; i <= n; ++i) {
while (qh < qt && slope(q[qh], q[qh + 1]) < p[i].x + 1) ++qh;
f[i] = f[q[qh]] + sqr(p[i].x - p[q[qh] + 1].y + 1) + C, cnt[i] = cnt[q[qh]] + 1;
if (i == n) break;
if (p[i + 1].y <= p[i].x) f[i] -= sqr(p[i].x - p[i + 1].y + 1);
while (qh < qt && slope(q[qt - 1], q[qt]) > slope(q[qt], i)) --qt;
q[++qt] = i;
}
return cnt[n];
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
ll ans = 0, l = 0, rr = (ll)m * m + 10;
for (int i = 0; i < n; ++i) {
if (r[i] < c[i]) p[i + 1].x = c[i], p[i + 1].y = r[i];
else p[i + 1].x = r[i], p[i + 1].y = c[i];
}
sort(p + 1, p + n + 1, cmp);
m = 0;
p[0].y = -1;
for (int i = 1; i <= n; ++i) {
while (m && p[m].y >= p[i].y) --m;
p[++m] = p[i];
}
n = m;
for (int i = 1; i <= n; ++i) {
ans += sqr(p[i].x - p[i].y + 1);
if (i < n && p[i + 1].y <= p[i].x) ans -= sqr(p[i].x - p[i + 1].y + 1);
}
if (n <= k) return ans;
while (l <= rr) {
ll mid = l + rr >> 1;
int res = solve(n, mid);
if (res <= k) rr = mid - 1, ans = f[n];
else l = mid + 1;
}
rr++;
ans -= rr * k;
return ans;
}