决策单调性

发表于 | 阅读数

决策单调性

$w(l,r)$

但当函数$w(l,r)$, 满足一些特殊的性质时，我们可以利用决策的单调性进行优化。

1D1D 动态规划中的应用

$f_r=min(f_l+w(l,r))$

假设$r_2>r_1$决策点$l_2<l_1$

则$l_2<l_1<r_1<r_2$

想加可得

与事实违背。

则$l_1\leq l_2$。
在这里我们根据决策单调性只能得出每次枚举 时的下界，而无法确定其上界。因此，简单实现该状态转移方程仍然无法优化最坏时间复杂度。

考虑分治算法。
$DP(l,r,L,R)$表示$f_l..f_r$的决策$\in [L,R]$

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(int l, int r, int L, int R)
{
    if (r < l)
        return;
    int mid = (l + r) >> 1;
    int maxn = 0, p;
    for (int i = L; i <= min(mid, R); i++)
        if (w(mid, i) > maxn)
            p = i, maxn = w(mid, i);
    dp[mid] = max(maxn, dp[mid]);
    solve(l, mid - 1, L, p);
    solve(mid + 1, r, p, R);
}

2D1D 动态规划中的应用

先贴个板子。

题目较少，日后来更新

1
2
3
4
5
6
7
8
9
10
for (int len = 2; len <= n; ++len)  // 枚举区间长度
  for (int l = 1, r = len; r <= n; ++l, ++r) {
    // 枚举长度为len的所有区间
    f[l][r] = INF;
    for (int k = m[l][r - 1]; k <= m[l + 1][r]; ++k)
      if (f[l][r] > f[l][k] + f[k + 1][r] + w(l, r)) {
        f[l][r] = f[l][k] + f[k + 1][r] + w(l, r);  // 更新状态值
        m[l][r] = k;  // 更新（最小）最优决策点
      }
  }