Description 从山顶上到山底下沿着一条直线种植了n棵老树。当地的政府决定把他们砍下来。为了不浪费任何一棵木材，树被砍倒后要运送到锯木厂。 木材只能按照一个方向运输：朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建两个锯木厂，使得传输的费用总和最小。假定运输每公斤木材每米需要一分钱。 你的任务是编写一个程序，从输入文件中读入树的个数和他们的重量与位置，计算最小运输费用。 Input 输入的第一行为一个正整数n——树的个数（2≤n≤20000）。树从山顶到山脚按照1，2……n标号。接下来n行，每行有两个正整数（用空格分开）。第i+1行含有：wi——第i棵树的重量（公斤为单位）和 di——第i棵树和第i+1棵树之间的距离，1≤wi≤10000，0≤di≤10000。最后一个数dn，表示第n棵树到山脚的锯木厂的距离。保证所有树运到山脚的锯木厂所需要的费用小于2000000000分。 Output 输出只有一行一个数：最小的运输费用。 Sample Input 9 12 21 33 11 32 16 21 12 11 Sample Output 26
这题本来在cogs上能交的，现在交不了了。。。以此题开始我们的斜率优化之旅。。。斜率优化是为了什么呢？是为了降低时间复杂度。像此题就是个1D/1D的方程，复杂度为 O(n2) ，过不去。怎么办呢？一维的状态我们是不可能再优化了，只可能优化决策。朴素的方程在下面有所介绍，这里直接借用。如果要求f[i]，我们要在所有的1<=j< i中寻找最优解，那有没有可能直接获得我们的最优决策呢？我们有一个大胆的想法：假设当前第二锯木厂设置在i，而它的最优决策为k，也就是说求出的f[i]值是当j取k时得到的，而对于f[i+1]的最优决策k1必然大于k。证明见下。 下面是演算过程： 令Sw[i]表示前i棵树的总重量, sw[i]=∑j=1iw[j] 令Sd[i]表示前i棵树的总距离， Sd[i]=∑j=1i−1d[j] c[i]表示第一个锯木厂建在i，把1…i-1棵树运到i所需的花费 C[i]=C[i−1]+Sw[i−1]∗d[i−1] w[i][j]表示把i…j-1棵树运到j的花费。 则w[i][j]=C[j]−C[i−1]−Sw[i−1]∗(Sd[j]−Sd[i−1]) 总的费用为 f[i]=min(C[j]+W[j+1][i]+W[i+1][n+1]|1<=j<i) 证明决策单调性： 设k1,k2分别为f[i]的两个决策，且k1< k2，G[i,k1],G[i,k2]分别为k1,k2得出的f[i]值，即 G[i,k1]=c[k1]+w[k1+1][i]+w[i+1][n+1] G[i,k2]=c[k2]+w[k2+1][i]+w[i+1][n+1] 那么, G[i,k1]−G[i,k2]=sw[k2]∗(sd[i]−sd[k2])−sw[k1]∗(sd[i]−sd[k1]). 若k2比k1优，即G[i,k1]-G[i,k2]>0,整理得 sw[k1]∗sd[k1]−sw[k2]∗sd[k2]sw[k1]−sw[k2]<sd[i] 设slope[k1,k2]=不等式左边，则对于k>i有slope[k1,k2]< sd[i]< sd[k]，也就是说如果k1在i时就不如k2优，那在以后k1也不可能比k2优。即满足决策单调性。（黑书上把这称为凸完全单调性，并用矩阵阐释了动态规划的本质，并提出了最小值行编号定理。大家感兴趣可以去阅读一下。）然后我们发现slope其实就是个斜率，以sw[k]为x坐标，sw[k]*sw[k]为y坐标的两个点k1,k2的斜率。所以叫他斜率优化。我们用一个队列来维护最优决策。对于此题而言，k1< k2,k1若想比k2优，则slope[k1,k2]> sd[i]，因为sd[i]是递增的，所以我们要保证队列中的slope也是递增的，即体现在形上就是维护一个下凸曲线。怎么维护详见这里 由于每个点进队出队都只有一次，所以复杂度是O(n)的，成功优化！
#include <cstdio> #include <cstring> #define inf 2000000000 //32MB--33554432B,不能开w[N][N] int const N=20000+10; int n,sw[N],sd[N],d[N],c[N],f[N],q[N],h=0,t=1; //c[i]表示在i建第一个锯木厂，把1~i-1运到i的花费； //w[i][j]表示第二个锯木厂建在i，第一个锯木厂建在j,把j+1~i-1运到i的花费 int read(){ int x=0;char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x; } inline int min(int x,int y){return x<y?x:y;} inline double slope(int k1,int k2){ return (sw[k2]*sd[k2]-sw[k1]*sd[k1])*1.0/(sw[k2]-sw[k1]); } int main(){ freopen("two.in","r",stdin); freopen("two.out","w",stdout); n=read(); for(int i=1;i<=n;++i){ int x=read();d[i]=read(); sw[i]=sw[i-1]+x; sd[i]=sd[i-1]+d[i-1]; } sd[n+1]=sd[n]+d[n];sw[n+1]=0; for(int i=1;i<=n+1;++i) c[i]=c[i-1]+sw[i-1]*d[i-1]; q[++h]=1; for(int i=2;i<=n;++i){//f[i]--把第二个锯木厂建在i的最小花费 while(h<t&&slope(q[h],q[h+1])<sd[i]) h++; f[i]=c[n+1]-sw[q[h]]*(sd[i]-sd[q[h]])-sw[i]*(sd[n+1]-sd[i]); while(h<t&&slope(q[t],i)<slope(q[t-1],q[t])) t--; q[++t]=i; } int ans=inf; for(int i=2;i<=n;++i) ans=min(ans,f[i]); printf("%d",ans); return 0; }