众所周知，初始化肯定比dp简单

但是我写出来了鞋油dp，但是却不理解为什么这个初始化寄了

跟题解的写法不太一样（我的是w递增，l递减排序，题解反之），但事实证明斜优部分是没有问题的（改成按照题解的初始化，然后Reverse一下就A了）

以下是错的

这里面我觉得结构体要写个点比较麻烦，所以我另开w,l数组再斜优前重新复制了一遍，没区别的
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,q[N],f[N],w[N],l[N];
struct Node{
    int w,l;
}a[N];
bool cmp(Node x,Node y){
    return x.w<y.w;
}
int X(int i){
	return -l[i];
} 
int Y(int i){
	return f[i];
}
int K(int i){
	return w[i-1];
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].w,&a[i].l);
    sort(a+1,a+n+1,cmp);
    int m=0;a[m].l=1e15;
    for(int i=1;i<=n;i++) 
    	if(a[i].l<a[m].l) a[++m]=a[i];
    n=m;
    for(int i=1;i<=n;i++) w[i]=a[i].w,l[i]=a[i].l;
    int hh=1,tt=0;
	q[++tt]=1,f[0]=1e15;
	for(int i=2;i<=n+1;i++){
		while(hh<tt&&Y(q[hh+1])-Y(q[hh])<=K(i)*(X(q[hh+1])-X(q[hh]))) hh++;
		int j=q[hh];
		f[i]=f[j]+l[j]*w[i-1];
		while(hh<tt&&(Y(i)-Y(q[tt]))*(X(q[tt])-X(q[tt-1]))<=(Y(q[tt])-Y(q[tt-1]))*(X(i)-X(q[tt]))) tt--;
		q[++tt]=i;
	}
	printf("%lld",f[n+1]);
    return 0;   
}

以下是正确的

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,q[N],f[N],w[N],l[N];
struct Node{
    int w,l;
}a[N];
bool cmp(Node x,Node y){
    return x.w>y.w;
}
int X(int i){
	return -l[i];
} 
int Y(int i){
	return f[i];
}
int K(int i){
	return w[i-1];
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].w,&a[i].l);
    sort(a+1,a+n+1,cmp);
    int m=0;
    for(int i=1;i<=n;i++)
        if(a[i].l>a[m].l) a[++m]=a[i];
    n=m;
    for(int i=1;i<=n;i++) w[i]=a[i].w,l[i]=a[i].l;
    for(int i=1;i<=n/2;i++) swap(w[i],w[n-i+1]),swap(l[i],l[n-i+1]);
    int hh=1,tt=0;
	q[++tt]=1,f[0]=1e15;
	for(int i=2;i<=n+1;i++){
		while(hh<tt&&Y(q[hh+1])-Y(q[hh])<=K(i)*(X(q[hh+1])-X(q[hh]))) hh++;
		int j=q[hh];
		f[i]=f[j]+l[j]*w[i-1];
		while(hh<tt&&(Y(i)-Y(q[tt]))*(X(q[tt])-X(q[tt-1]))<=(Y(q[tt])-Y(q[tt-1]))*(X(i)-X(q[tt]))) tt--;
		q[++tt]=i;
	}
	printf("%lld",f[n+1]);
    return 0;   
}

只要对我有一点启发都会关注，谢谢~