目录
BZOJ1096 仓库建设题解ｃｏｄｅ
BZOJ1096 仓库建设
题目传送门
题解
也是一道比较经典的斜率优化\(Dp\)，很容易推出DP转移方程：\(dp[i]=min(dp[j]+cost(i,j))+c[i]\)
重点就是怎么快速的算出cost(i,j)。我们把cost的计算公式写出来：\(cost(i,j)=\sum_{k=j+1}^ip[k]*(x[i]−x[k])＝x[i]*\sum_{k=j+1}^ip[k]-\sum_{k=j+1}^ip[k]*x[k]\)
我们记sum[i]为p[i]的前缀和，b[i]为p[i]∗x[i]的前缀和，那么DP转移就是：\(dp[i]=min(dp[j]+x[i]*(sum[i)−sum[j])−(b[i])−b[j])+c[i]\)
于是我们就可以愉悦的用斜率优化来做这道题了，如果k>j并且k比j更优，那么：\(dp[j]+x[i]*(sum[i]sum[j])−(b[i])−b[j]≥dp[k]+x[i]*(sum[i)−sum[k])−(b[i])−b[k]\)
整理一下可得：\(dp[k]−dp[j]+b[k]−b[j]sum[k]−sum[j]≤s[i]\)
最后就是套用斜率优化的步骤了。
ｃｏｄｅ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
const int maxn=1e6+500;
int n;
ll dis[maxn],c[maxn],p[maxn],f[maxn],sum[maxn],b[maxn];
int l,r;
int que[maxn];
/*==================Define Area================*/
double Cal(int x,int y) {
return (double)(f[y]-f[x]+b[y]-b[x])/(double)(sum[y]-sum[x]);
}
int main() {
read(n);
for(int i=1;i<=n;i++) {
read(dis[i]);read(p[i]);read(c[i]);
}
for(int i=1;i<=n;i++) {
sum[i]=sum[i-1]+p[i];
b[i]=b[i-1]+p[i]*dis[i];
}
for(int i=1;i<=n;i++) {
while(l<r&&Cal(que[l],que[l+1])<dis[i]) l++;
int t=que[l];
f[i]=f[t]-b[i]+b[t]+(sum[i]-sum[t])*dis[i]+c[i];
while(l<r&&Cal(que[r-1],que[r])>Cal(que[r],i)) r--;
que[++r]=i;
}
printf("%lld\n",f[n]);
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9434923.html
相关资源：JAVA上百实例源码以及开源项目
