决策单调性

还是考虑 $f[i,j]=\min_{k < i} { f[k,j - 1] + w[k+1,i] }$

之前的循环顺序是：for(i=1:n){for(j=1:k){}}

也可以内外循环交换一下：for(j=1:k){for(i=1:n){}}

由四边形不等式可得：$p[i,k-1] \le p[i,k]$，即每一行的决策点是单调的

既然决策是单调的，那么在计算 $f[l] \sim f[r]$ 时，可以先计算 $f[(l+r)/2]$ ，这样 $[l,m-1],[m+1,r]$ 的决策点范围就会进一步缩小

于是总时间复杂度就降为了 $O(kn \log n)$

void dfs(int l, int r, int pl, int pr) {
  if(l > r) return ;
  int mid = (l + r) >> 2;
  int pmid; f[mid][j] = inf;
  for(int k = pl ; k <= min(pr, mid) ; ++ k) {
    auto g = f[k][j - 1] + w(k + 1, mid);
    if(g <= f[mid][j]) {
      f[mid][j] = g;
      pmid = k;
    }
  }
  dfs(l, mid - 1, pl, pmid);
  dfs(mid + 1, r, pmid, pr);
}

进而，可以扩展到解决 $f[i]=\min_{j < i}{ f[j]+w[j+1,i] }$ 这一类问题

分治算法的思想是固定待求值点，寻找决策区间，如果反过来考虑呢？

对于每一个决策点，寻找以它为决策点的决策区间

显然对于决策点 $x < y$，有 $l_x \le r_x < l_y \le r_y$

那么可以开一个deque，一开始存入 { 1, n, 0 } 表示决策点 $0$ 对应决策区间 $[1,n]$

换句话说，我们只关心已经计算出来的 $f[i]$ 对未计算出来的所有 $j > i$ 的影响

struct META { int l, r, p; }; // f[p] orders [l, r]
deque<META> q;
for(int i = 1 ; i <= n ; ++ i) {
  while(q.size() && q.front().r < i) q.pop_front();
  if(chk(i, n) <= chk(q.back().p, n)) {
    while(q.size() &&
          chk(i, q.back().l) <= chk(q.back().p, q.back().l))
      q.pop_back();
    if(q.empty()) q.push_back((META) { i + 1, n, i });
    else {
      int x = [&] (int od, int nw, int l, int r) {
        int res = l;
        while(l <= r) {
          int mid = (l + r) >> 1;
          if(chk(nw, mid) <= chk(od, mid)) {
            res = mid;
            l = mid + 1;
          } else r = mid - 1;
        }
        return res;
      } (q.back().p, nw, q.back().l, q.back().r);
      q.back().r = x - 1;
      q.push_back((META) { x, n, i });}}}

[HNOI2008]玩具装箱

有 $n$ 个物品排成一排，第 $i$ 个物品有价值 $c_i$
现在要求将物品序列分成若干段，每一段的代价是 $(r-l-L+\sum _ {i=l}^{r}c _ i)^2$
求最小代价
$1 \le n \le 5 \times 10^4$

设 $f[i]$ 表示前 $i$ 个物品划分成若干段的最小代价

$$
\begin{cases}
f[i]=\min _ {j \le i}{ f[j-1]+w[j,i]} \\
w[j,i]=(i-j-L+s[i]-s[j-1])^2
\end{cases}
$$

四边形不等式：$w[i,j]+w[i+1,j+1] \le w[i+1,j]+w[i,j+1]$

~~不证了，展开后反正满足四边形不等式~~

于是决策是单调的，套用上面的分治或单调队列模板即可

「POI2011 R1」避雷针 Lightning Conductor

给定长度为 $n(\le 5 \times 10^5)$ 的序列 ${a_n}$
求数组 $f$，满足 $f_{i}=\max_{j=1}^{n}{ a[i]-a[j]+\sqrt{|i-j|} }$

只需要考虑 $j < i$ 的情况（$j > i$ 同理）

$w[i,j] = \sqrt{j - i} + a[j] - a[i]$

（反）四边形不等式：$w[i,j]+w[i+1,j+1] \ge w[i+1,j]+w[i,j+1]$

$$
\begin{aligned}
&w[i+1,j]+w[i,j+1]-w[i,j]-w[i+1,j+1] \\
=&\sqrt{j-i-1}+\sqrt{j+1-i}-2\sqrt{j-i} \\
&+a[j]-a[i+1]+a[j+1]-a[i]-a[j] \\
&+a[i]-a[j+1]+a[i+1] \\
=&\sqrt{j-i-1}+\sqrt{j+1-i}-2\sqrt{j-i} \\
=&\sqrt{x-1}+\sqrt{x+1}-2\sqrt{x} \le 0
\end{aligned}
$$

接着上面那个题 Chef and Bitwise OR Operation，能不能再挖掘一下性质？

决策单调性优化dp

决策单调性

[HNOI2008]玩具装箱

「POI2011 R1」避雷针 Lightning Conductor

题单