luogu P4360 [CEOI2004]锯木厂选址

斜率优化dp板子题[迫真]

这里从下往上标记\(1-n\)号点

记\(a_i\)表示前缀\(i\)里面树木的总重量,\(l_i\)表示\(i\)到最下面的距离,\(s_i\)表示\(1\)到\(i-1\)号树运到最下面的代价(就是下面那个伐木厂产生的代价),\(f_i\)表示上面那个伐木厂在\(i\),\(1\)到\(i-1\)号树产生的代价

我们可以用脚列出式子$$f_i=min(s_j+(s_i-s_{j+1})-l_j(a_{i-1}-a_j))$$

就是下面那个伐木厂产生的代价\(s_j\)+两个伐木厂之间的树(\(j+1\)到\(i-1\))产生的代价,记为\(g\)(\(s_i=s_{j+1}+g+l_j(a_{i-1}-a_j)\))

然后把式子展开$$f_i=min(s_j+s_i-s_{j+1}-l_ja_{i-1}+l_ja_j)$$

设\(A_i=s_i-s_{i+1}+l_ia_i\)

原式变为$$f_i=min(A_j+s_i-l_ja_{i-1})$$

假定决策\(j\)优于决策\(k\),有$$A_j+s_i-l_ja_{i-1}< A_k+s_i-l_ka_{i-1}$$

可以化简为$$a_{i-1}<\frac{A_k-A_j}{l_k-l_j}$$

开单调队列维护一个下凸壳,每次先把队首的斜率小于\(a_{i-1}\)的弹掉,然后用队首转移,把\(i\)插入队尾,把斜率过高的弹掉

还不会就参考P3195救星了

不是我懒得写,是因为我怕再写就扯不清楚了,还有前面的分析很详细了不是吗qwq

#include<bits/stdc++.h>

#define LL long long

#define il inline

#define re register

#define db double

using namespace std;

const int N=20000+10;

il LL rd()

{

    re LL x=0,w=1;re char ch;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int n;

LL a[N],s[N],l[N],f[N],ans=2333333333;

//M_sea&Qihoo360

il db A(int i){return s[i]-s[i+1]+a[i]*l[i];}

il db K(int j,int k){return (db)(A(k)-A(j))/(db)(l[k]-l[j]);}

//IOI

int main()

{

  n=rd();

  for(int i=n;i>=1;i--) a[i]=rd(),l[i]=rd();

  for(int i=1;i<=n;i++) l[i]+=l[i-1],s[i]=s[i-1]+a[i]*l[i],a[i]+=a[i-1];

  for(int i=n+1;i>=2;i--) s[i]=s[i-1];s[1]=0;

  int q[N],hd=1,tl=1;

  q[1]=0;

  for(int i=1;i<=n;i++)

    {

      while(hd<tl&&K(q[hd],q[hd+1])<=(db)(a[i-1])) ++hd;

      f[i]=s[q[hd]]+(s[i]-s[q[hd]+1])-(a[i-1]-a[q[hd]])*l[q[hd]];

      ans=min(ans,f[i]+(s[n+1]-s[i+1])-(a[n]-a[i])*l[i]);   //对于每个f[i]更新答案

      while(hd<tl&&K(q[tl],q[tl-1])>=K(i,q[tl-1])) --tl;

      q[++tl]=i;

    }

  printf("%lld\n",ans);

  return 0;

}