求助样例过不去,跟题解已经只差变量名了
查看原帖
求助样例过不去,跟题解已经只差变量名了
578029
ivyjiao楼主2024/8/31 15:33
//sort l为第一关键字,从小到大,w为第二关键字,从小到大
//dp[i] = min(dp[j]+l[i]*w[j+1])
//dp[i] = dp[j]+l[i]*w[j+1]
//dp[i] = l[i]*w[j+1]+dp[j]
//dp[j] = -l[i] * w[j+1] + dp[i]
//  y   =   k   *   x    +  b
//启动!
#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;
int n,m,dp[50001],q[50001];
PII a[50001],b[50001];
bool cmp(PII x,PII y){
    if(x.fi==y.fi) return x.se<y.se;
    return x.fi<y.fi;
}
int X(int j){
	return b[j+1].se;
}
int Y(int j){
	return dp[j];
}
double query(int i,int j){
	return 1.0*(Y(j)-Y(i))/(X(i)-X(j));
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].fi>>a[i].se;
    sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
        while(m&&a[i].se>=b[m].se) m--;
        b[++m]=a[i];
    }
    int h=0,t=1;
	for(int i=1;i<=m;i++){
		while(h<t&&query(q[h],q[h+1])<=-b[i].fi) h++;
		dp[i]=dp[q[h]]+b[i].fi*b[q[h]+1].se;
		while(h<t&&query(q[t-1],i)<=query(q[t-1],q[t])) t--;
		q[++t]=i;
        //cout<<dp[i]<<endl;
	}
	cout<<dp[n];
}
2024/8/31 15:33
加载中...