斜率优化 20pts 求调
查看原帖
斜率优化 20pts 求调
685964
shuqiang楼主2025/7/21 14:16
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 2e5 + 10, V = 1e6+1;
int n; ll f[N];

struct pii{
	ll x, y;
	
	bool operator < (const pii & o) const{
		if(x == o.x) return y < o.y;
		return x < o.x;
	}
} a[N]; vector<pii> lst;
deque<pii> q; 

ld get_k(ll ax, ll ay, ll bx, ll by){
	return (ld)(ay - by) / (ax - bx);
}

int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i].x >> a[i].y;
	}
	sort(a + 1, a + 1 + n);
	
	lst.push_back({0, V});
	for(int i = 1; i <= n; i++){
		while(a[i].y > lst.back().y) lst.pop_back();
		lst.push_back(a[i]);
	}
	
//	cout << '\n';
//	for(int i = 1; i < lst.size(); i++){
//		cout << lst[i].x << ' ' << lst[i].y << '\n';
//	}
	
	for(int i = 1; i < lst.size(); i++){
//		f[i] = (ll)lst[i].x * lst[i].y + f[i-1];
		while(q.size() >= 2){
			pii tp = q.back();
			q.pop_back();
			if(get_k(q.back().x, q.back().y, tp.x, tp.y) > get_k(tp.x, tp.y, lst[i].y, f[i-1])){
				q.push_back(tp);
				break;
			}
		}
		q.push_back((pii){lst[i].y, f[i-1]});
		
		while(q.size() >= 2){
			pii tp = q.front();
			q.pop_front();
			if(get_k(tp.x, tp.y, q.front().x, q.front().y) <= -a[i].x){
				q.push_front(tp);
				break;
			}
		}
		f[i] = q.front().y + (ll)lst[i].x * q.front().x;
		
//		for(int j = 1; j < i; j++){
//			f[i] = min(f[i], f[j-1] + (ll)lst[i].x * lst[j].y);
//		}
	}
//	for(int i = 1; i < lst.size(); i++) cout << f[i] << ' ';
//	cout << '\n';
	cout << f[lst.size()-1] << '\n';
	return 0;
}

2025/7/21 14:16
加载中...