目录
斜率优化dp
H.仓库建设
思路
很容易想暴力，因为只能往后送物资，从后往前计算dp[i]为在i这里建造仓库且i~n都有地可去的最小价值
为了方便计算，我把x[i]修改为到n节点的距离，用f维护p[i]*x[i]的后缀和，num维护p[i]后缀和
那么方程为
推式子得，若j1<j2且j1优于j2，必然满足
\[num[i+1]\ge\tfrac{Y(j2)-Y(j1)}{X(j2)-X(j1)} \]其中$$ Y(j)=dp[j]+x[j]*num[j]-f[j]$$
\[X(j)=x[j] \]代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define N 1000005
#define ll long long
inline int read(){
int x=0,f=1; char c=getchar();
while(c>'9'||c<'0'){if(c=='-') f=-1; c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^'0'); c=getchar();}
return x*f;
}int n;
ll dp[N],x[N],p[N],c[N];
ll inf=99999999999999;
ll f[N],num[N];
int tmp[N];
ll Y(int w1){
return dp[w1]+x[w1]*num[w1]-f[w1];
}ll X(int w1){
return x[w1];
}
double s(int w1,int w2){
if(X(w2)==X(w1)) return inf;
return 1.0*(1.0*(Y(w2)-Y(w1))/(X(w2)-X(w1)*1.0));
}
int main(){
// freopen("1.txt","r",stdin);
n=read();
for(int i=0;i<=n;i++) dp[i]=inf;
for(int i=1;i<=n;i++){
x[i]=read(),p[i]=read(),c[i]=read();
}//while(!p[n]) n--;
int lmy=x[n];
for(int i=1;i<=n;i++) x[i]=lmy-x[i];
for(int i=n;i>=1;i--){
f[i]=f[i+1]+p[i]*x[i];
num[i]=num[i+1]+p[i];
// cout<<f[i]<<" "<<num[i]<<endl;
}
int h=1,t=0;
tmp[++t]=n;
dp[n]=c[n];
for(int i=n-1;i>=0;i--){
while(h<t&&(s(tmp[h],tmp[h+1])<=num[i+1])) h++;
int j=tmp[h];
dp[i]=min(dp[i],(dp[j]+(f[i+1]-f[j])-x[j]*(num[i+1]-num[j])+c[i]));
while(h<t&&(s(tmp[t-1],tmp[t])>=s(tmp[t],i))) t--;
tmp[++t]=i;
}printf("%lld\n",dp[0]);
return 0;
}
J.土地购买
思路:
排序后处理掉没用的块，然后就能保证l单调减，r单调增，此时保证所选择的块一定呆在一起，可以用假设法证明，如果最优解不相邻，那么中间的不优，矛盾，得证
然后可以列出方程：
假设\(j1<j2\)并且\(j2优于j1\)，此时可以将\(j1\)从队首弹出，必然满足
\[qwq[i].r\ge\tfrac{dp[j2]-dp[j1]}{qwq[j1].l-qwq[j2].l} \]代码
点击查看代码
sort(s+1,s+n+1,cmp);
ll max_r=0;
for(int i=1;i<=n;i++){
if(max_r>=s[i].r) continue;
max_r=max(max_r,s[i].r);
qwq[++q]=s[i];
}
int t=1,h=1;
for(int i=1;i<=q;i++){
while(h<t&&ss(tmp[h],tmp[h+1])<=qwq[i].r)
h++;
int j=tmp[h];
dp[i]=min(dp[i],dp[j]+qwq[j+1].l*qwq[i].r);
while(h<t&&ss(tmp[t-1],tmp[t])>=ss(tmp[t],i)) t--;
tmp[++t]=i;
}
printf("%lld\n",dp[q]);