斜率优化 WA 20 求调
查看原帖
斜率优化 WA 20 求调
857626
_RainCappuccino_楼主2025/7/1 10:27
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
#define int long long
#define endl '\n'
const int N = 5e4 + 10;
int n, m;
pi a[N], b[N];
int x[N], y[N], f[N];
double slope (int i, int j) {
	return (double)(y[j] - y[i]) / (x[j] - x[i]);
}
#define he first
#define we second
int q[N], h, t;

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i ++)
		cin >> a[i].he >> a[i].we;
	sort (a + 1, a + 1 + n, greater<pi>());
	for (int i = 1; i <= n; i ++)
		if (a[i].we > a[m].we) a[++ m] = a[i];
    n = m;
	// first 单减,second 单增
	for (int i = 1; i <= n; i ++) {
		int k = -a[i].we; // 单增
		while (h < t && slope(q[h], q[h + 1]) >= k) h ++;
		f[i] = f[q[h]] + a[i].we * a[q[h] + 1].he;
		x[i] = a[i + 1].he, y[i] = f[i];
		while (h < t && slope(q[t - 1], q[t]) <= slope(q[t], i)) t --;
		q[++ t] = i;
	}
    cout << f[n];
	return 0;
}
/*
b = y - kx
f[i] = f[j] + h[j + 1] \times w[i]

y = f[j] x = h[j + 1] k = -w[i]
*/
2025/7/1 10:27
加载中...