[洛谷 3195][HNOI2008]玩具装箱

题目链接

https://www.luogu.org/problem/P3195

题解

斜率优化基础题。

设 \(s_i\) 为 \(c_i\) 的前缀和,\(f_i\) 为前 \(i\) 个物品的最小代价,不难推出这样的状态转移方程:

$$f_i=\min_{1 \leq j < i}{f_j+(s_j-s_i+i-j-1+L)^2}$$

然而这样转移的复杂度是 \(O(n^2)\) 的,在 \(n=50000\) 的数据面前还是需要优化。

首先让我们整理一下式子,令 \(A_i=s_i+i\),\(B_i=s_j+j+1+L\),则原转移方程可以化简成这样的形式:

$$f_i=\min_{1 \leq j < i}{f_j+(A_i-B_j)^2}$$

假如在 \(i\) 处存在两个决策点 \(x,y\),满足 \(x>y\) 时,且 \(x\) 处的决策比 \(y\) 处更优。

我们可以写出一个不等式:

$$f_x+(A_i-B_x)^2<f_y+(A_i-B_y)^2$$

$$f_x+A_i^2+B_x^2-2A_iB_x<f_y+A_i^2+B_y^2-2A_iB_y$$

$$\frac{f_x+B_x^2-f_y-B_y^2}{B_x-B_y}<2A_i$$

左边式子的物理含义是比较明显的,它代表了一个一次函数的斜率,斜率优化的名称就由此而来。

我们接下来结合线性规划的知识来理解斜率优化。

假如目标函数(也就是直线)的斜率为 \(k\),我们可以证明,当决策点左边的直线斜率均小于 \(k\),右边直线斜率的直线均大于 \(k\) 时,该决策点是最优的决策点。在平面直角坐标系里表示的话,当目标直线与凸壳在上面所述的决策点处相切的时候,直线在 \(y\) 轴上的截距最小,即目标函数取得最小值。

现在算法的思路就清晰了,我们用单调队列来维护一个斜率递增的下凸壳,在每个状态 \(i\) 执行如下过程:

  1. 如果队首两点对应的直线斜率小于 \(2A_i\),根据上文所述,该直线就变得无用了,我们将队首弹出队列。
  2. 我们找到的第一条斜率大于 \( 2A_i \) 的直线的左端点将会成为该状态的最优决策。(经过第 \(1\) 步的处理后,最优决策点一定会在队首)
  3. 我们接下来把当前状态 \(i\) 加入下凸壳中。注意到新加入的点可能会破坏凸壳斜率递增的性质,因此我们要检查队尾两点对应的直线斜率,如果不满足斜率递增性质,就将队尾出队,直到满足斜率递增或队列为空再将当前点 \(i\) 加入队列当中。

因为每个状态最多入队一次,出队一次,算法的复杂度是 \(O(n)\) 的。


做完 诗人小G 之后,你会发现,本题事实上是那道题目的特例。

当代价的幂次从 \(2\) 扩展到任意整数时,斜率优化便不再适合了,但我们可以通过证明决策单调性来解决这个更一般性的问题。

(这部分的内容先咕了,以后再填坑)

#include <iostream>
using namespace std;
long long s[50005],q[50005],f[50005],l,r,n,len;
long long a(int x)
{
 return s[x]+x;
}
long long b(int x)
{
 return s[x]+x+1+len;
}
double slope(int x,int y)
{
 long long bx=b(x),by=b(y);
 return double(f[x]+bx*bx-f[y]-by*by)/(bx-by);
}
int main()
{
 cin>>n>>len;
 for(int i=1;i<=n;i++)
 {
  int x;
  cin>>x;
  s[i]=s[i-1]+x;
 }
 for(int i=1;i<=n;i++)
 {
  while(l<r&&slope(q[l+1],q[l])<=2*a(i))
   l++;
  f[i]=f[q[l]]+(a(i)-b(q[l]))*(a(i)-b(q[l]));
  while(l<r&&slope(q[r],q[r-1])>slope(i,q[r]))
   r--;
  q[++r]=i;
 }
 cout<<f[n]<<endl;
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注