跟 Nachia 博客学 DP-18 插入 DP

常见于排列计数问题：

当计算有关于序列 $A$ 的整个排列时候：

• $\text{dp}[i] :=$ （已经确定了序列第 $i$ 小项在排列前后关系状态中的小问题的解）

简单来讲，让 $A$ 升序排序之后，按顺序插入时，因为有值的单调性，于是根据插入位置的不同来求解的动态规划问题。

当相邻项之间存在约束时，有一种模式是在计算时将不满足约束的相邻位置数量的信息作为下标持有。

例子1:T - Permutation

https://atcoder.jp/contests/dp/tasks/dp_t

$f_{i,j} :=$ 插入了 $i$ 个数字，最后一个数字的排名是 $j$ 的方案数

插入的元素一定比新元素大，所以插入进去的话，只需要考虑原本的最后一个数字的排名即可.

如果要求 $p_2\gt p_3$ 的话，可以插入成这两种：(2,3,1), (1,3,2)

而这两种的转移刚好是 $f_{2,1}$ 和 $f_{2,2}$

小于的话等价，于是我们就有转移
$$
f_{i+1,j+1} = \sum_{k=1}^j f_{i,k}
$$

$$ f_{i+1}{j}=\sum_{k=j}^if_{i,k} $$

因为如果是 > 的话，不会更新最后一位的排名.

  LL(N); STR(S);
  V f(N + 1, V<mm>(N + 1, 0));
  f[1][1] = 1;
  rep(i, N) {
    if(S[i - 1] == '<') {
      mm S = 0;
      rep(j, 1, i + 1) {
        S += f[i][j];
        f[i + 1][j + 1] += S;
      }
    } else {
      mm S = 0;
      rrep(j, 1, i + 1) {
        S += f[i][j];
        f[i + 1][j] += S;
      }
    }
  }
  mm ans = 0;
  rep(i, 1, N + 1) ans += f[N][i];
  wt(ans);

例2: Ex - Group Photo

https://atcoder.jp/contests/abc313/tasks/abc313_h

ATC 红 题

固定前排排列后，每个后排位置都有一个身高门槛。中间位置的门槛是两侧前排身高的较小值，两端位置的门槛是唯一相邻的前排身高。把所有门槛和后排身高分别升序排序，逐一配对。如果第 (k) 矮的后排人无法超过第 (k) 小的门槛，就只有至多 (N+1-k) 个后排人能满足剩下的 (N+2-k) 个门槛。因此，升序配对成功当且仅当这个前排排列合法。

将前排身高 (A) 从小到大排序，做插入 DP。设 $f_{i,j}$ 表示已经放了最矮的 (i) 个人，他们在最终排列中形成 (j) 个连续块，且已确定的门槛都通过配对检查的方案数。每个块里每人左边有一个后排位置，块的右端再多一个封口位置，所以已确定的门槛共有 (i+j) 个。块边上即使还有空位，将来填进去的人也更高，因此这些门槛已经确定。

插入 A[i] 时，按它接到几个旧块分类：

每次把 (f_{i,j}) 乘以对应的选择数，加到下一层。转移后若有 (j') 块，剩下的人必须至少有 (j'-1) 个，才能填满块之间的空位。若这一步新增了门槛，它们都等于 A[i]。此前已有 (i+j) 个更小的门槛，因此只需检查升序后排数组中的 B[i+j] > A[i]，这一批最矮的人够高，其余也够高。

初始 (f_{0,0}=1)，答案为 (f_{N,1})。每个完整前排排列按身高从矮到高逐步显露时，都唯一确定每一步的插法，因此恰好计数一次。时间复杂度为 (O(N^2))，二维表空间为 (O(N^2))，可用滚动数组降到 (O(N))。

  LL(N); VEC(ll, A, N); VEC(ll, B, N + 1);
  sort(all(A)), sort(all(B));
  V f(N + 1, V<mm>(N + 1, 0));
  f[0][0] = 1;
  rep(i, N) rep(j, i + 1) rep(op, 3) {
    if(op > j) break;
    if(i + j + 2 > N + 1 + op) continue;
    if(op <= 1 && B[i + j] < A[i]) continue;
    mm cnt = 0;
    if(op == 0) 
      cnt = j + 1;
    elif(op == 1)
      cnt = 2 * j;
    else
      cnt = j - 1;
    debug(cnt);
    f[i + 1][j + 1 - op] += f[i][j] * cnt; 
  }
  wt(f[N][1].val());