发布时间：2024-07-31

斜率优化dp

写出dp方程，一般来说，需要O(n^2)的复杂度来遍历前面的状态
将j与i互换，变与不变列出y=kx+b的形式
实际为维护一个凸包;
- 若斜率大于0且单调递增,则可以每次将队头小于斜率的弹出
- 否则，需要二分寻找第一个大于的斜率例子：
  dp方程：
  $ f_i =min(f_j+sumt_i \cdot (sumc_i-sumc_j)+s \cdot (sumc_N-sumc_j))$
  整理得： $ f_j=(sumt_i+s) \cdot sumc_j +f_i-sumt_i \cdot sumc_j-s \cdot sumc_N $
  把 $ f_j $ 换成y, $ sumc_j $ 换成x,可转换成y=kx+b,对于一个确定的i有一个固定的斜率k且k>0,只需b尽可能小
将队头小于当前斜率的点删除,即$ \frac{f_{hh+1}-f_{hh}}{c_{hh+1}-c_{hh}}<=t_i+s $的点删除
单调增，即删除队尾$ \frac{f_{tt}-f_{tt-1}}{c_{tt}-c_{tt-1}}>=\frac{f_i-f_{tt}}{c_i-c_{tt}} $的点

cpp

void solve(){
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        cin>>t[i]>>c[i];
        t[i]+=t[i-1];
        c[i]+=c[i-1];
    }
    memset(f,0x3f,sizeof f);
    f[0]=0;
    int hh=0,tt=0;//队列
    //解释：tt=0是因为初始队列有一个元素0，是hh<tt而不是hh<=tt是因为要保证队列内值少有两个点
    for(int i=1;i<=n;i++){
        while(hh<tt&&f[q[hh+1]]-f[q[hh]]<=(t[i]+s)*(c[q[hh+1]]-c[q[hh]]))hh++;
        int j=q[hh];
        f[i]=f[j]+t[i]*(c[i]-c[j])+s*(c[n]-c[j]);
        while(hh<tt&&(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt]])>=(f[i]-f[q[tt]])*(c[q[tt]]-c[q[tt-1]]))tt--;
        q[++tt]=i;
    }
    cout<<f[n];
}

上面代码只能过掉t>0的情况，当t<0时斜率可能为负

斜率不再具有单调性，但横坐标仍具有单调性
查询的时候二分查找
删除时删去不是凸包的点

cpp

void solve(){
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        cin>>t[i]>>c[i];
        t[i]+=t[i-1];
        c[i]+=c[i-1];
    }
    memset(f,0x3f,sizeof f);
    f[0]=0;
    int hh=0,tt=0;//队列
    //解释：tt=0是因为初始队列有一个元素0，是hh<tt而不是hh<=tt是因为要保证队列内值少有两个点
    for(int i=1;i<=n;i++){
        int l=hh,r=tt;
        while(l<r){
            int mid=l+r>>1;
            if(f[q[mid+1]]-f[q[mid]]>(t[i]+s)*(c[q[mid+1]]-c[q[mid]]))r=mid;
            else l=mid+1;
        }
        int j=q[r];
        f[i]=f[j]+t[i]*(c[i]-c[j])+s*(c[n]-c[j]);
        while(hh<tt&&(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt]])>=(f[i]-f[q[tt]])*(c[q[tt]]-c[q[tt-1]]))tt--;
        q[++tt]=i;
    }
    cout<<f[n];
}

如果横坐标仍然不递增，则需要上通解
使用李超线段树
重写dp式子， $f_i=T_iC_i+SC_N+(-C_j(T_i+S)+f_j)$ ，括号里面的是一个直线解析式，用李超线段树维护直线即可
注意将查询的很坐标离散化，若求最小值，改变modify即可
复杂度： $O(n \log n)$

cpp

vector<int> nums={0};
struct LichaoTree{
	struct Line{
        int k,b;
		int f(int x){
            return k*nums[x]+b;
		}
	};
	vector<int> t;
	vector<Line> line;
    int n;
	void init(int n){
        t.assign(n+1<<2,0);
		line.push_back({0,INF});
        this->n=n;
    }
	void modify(int p,int l,int r,int id){
        int mid=l+r>>1;
        if(line[id].f(mid)<line[t[p]].f(mid))swap(t[p],id);
        if(l==r)return;
        line[id].f(l)<line[t[p]].f(l)?modify(p<<1,l,mid,id):modify(p<<1|1,mid+1,r,id);
	}
	int query(int p,int l,int r,int x){
        int res=line[t[p]].f(x);
		if(l==r)return res;
		int mid=l+r>>1;
        auto tmp=x<=mid?query(p<<1,l,mid,x):query(p<<1|1,mid+1,r,x);
		return min(res,tmp);
	}
    int query(int x){
        return query(1,1,n,x);
    }
    void add(int k,int b){
        line.push_back({k,b});
        modify(1,1,n,line.size()-1);
    }
} tr;
void solve(){
    int n,s;
    cin>>n>>s;
    vector<int> t(n+1),c(n+1),f(n+1);
    for(int i=1;i<=n;i++){
        cin>>t[i]>>c[i];
        t[i]+=t[i-1];
        c[i]+=c[i-1];
        nums.push_back(t[i]+s);
    }
    sort(nums.begin()+1,nums.end());
    nums.erase(unique(nums.begin()+1,nums.end()),nums.end());
    tr.init(nums.size());
    tr.add(0,0);
    for(int i=1;i<=n;i++){
        int j=lower_bound(nums.begin()+1,nums.end(),t[i]+s)-nums.begin();
        f[i]=t[i]*c[i]+s*c[n]+tr.query(j);
        tr.add(-c[i],f[i]);
    }
    cout<<f[n]<<"\n";
}

斜率优化dp ​

斜率优化dp