Fourth day

Zero_Sky · 2020-09-10 18:49:08 · 个人记录

数位DP

• 定义：给定区间 l 到 r ，在 l 到 r 内共有多少个满足条件的数

可以先做一个前缀和，则 [l,r] 可以看成 [0,r] - [0,l-1]
所以可以转化为

• \color{orange}0\ \text{到}\ x\ \text{之间有多少个满足条件的数}

求 [0,x] 里面数的个数
将 x 按位写下来 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \overline{x_kx_{k-1}x_{k-2} \cdots x_{1}}
找一个 0≤y≤x 按位写成 \overline{y_ky_{k-1}y_{k-2} \cdots y_1}

也就是找到 y_ky_{k-1}y_{k-2} \cdots y_1 总共有多少种可能使得 y≤x

DP方式就是\color{orange}\text{从高位向低位一位一位地赋值}

• \color{pink}\text{以上是数位DP统一的设计方式}

• 初始化 f[k+1][1] = 1 填到了 k + 1 位
• 转移
  1. f[i][0] += f[i-1][0]

  2. for(int j = 0; j <= x[i-1]; j++)
     {
         f[i - 1][x[i - 1] == j] += f[i][j];
     }

     当前 x 与 y 的大小关系取决于在 y_{i-1} 位上填的数 j ，如果 j 比 x_{i-1} 小，那么关系就从 等于 变成 小于，如果 j 等于 x_{i-1} 那么依然是相等关系所以第二维状态的转移为 x[i - 1] == j

• 最终的答案就是 f[1][0] + f[1][1]

\color{pink}\text{数位DP的套路}

1. 前缀和转化：
   由求 [l,r] 转化为求 [0,r] - [0,l]
2. 状态设计： f[i][j] $j$ 表示填完当前的位后 $\begin{cases}\text{0代表} <x \text{ 决定下一位可以填 0-9}\\ \text{1代表} =x \text{ 决定下一位可以填 0-}x_{i-1}\\\end{cases}
3. 初始化： x$ 有 $k$ 位，$f[k+1][1] = 1
4. 状态转移：
   枚举 i - 1 位填什么即可

• 求数的每一位

  int k = 0;
  while(x != 0)
  {
      y[++k] = x % 10;
      x = x / 10;
  }

例题

• 求在 [L,R] 中的数的数位之和
  （注：数位之和表示数的每一位加和，例如123的数位置和为1+2+3=6）

• 需要求前缀和，即 [L,R] = [0,R] - [0,L]

• 状态： f[i][j] 和 g[i][j]

  $g[i][j]$ 表示当前已经填的数的各个数位之和

• 转移：

  for(int i = k + 1; i >= 2; i--){
      for(int j = 0; j <= l; j++){
          for(int r = 0; r <= 9; r++){
              if(j == 1 && r > y[i - 1]) continue;
              f[i - 1][j != 0 && (r == y[i - 1])] += f[i][j];
              g[i - 1][j != 0 && (r == y[i - 1])] += g[i][j] + f[i][j] * r;
          }
      }
  }

  答案就是 g[1][0] + g[1][1]

• 求在 [L,R] 中的满足相邻两个数字之差至少为2的数有多少个

在上一问的基础上增加一维， k 表示第 i 位填的数是什么
即， f[i][j][k]

同时，除此之外还需要 \color{orange}\text{考虑前导零} ，例如：0001357是合法的

• 对于一个 n 位数 \overline{x_1x_2x_3\cdots x_n} ，
  函数 f(x) = |x_1 - x_2| + |x_2 - x_3| + \cdots + |x_{n - 1} - x_n|
• 求，在 [L,R] 之间一个找一个 x 使得 f(x) 的值最大

求 [L,R] 之间的一个 max ，因此不能用前缀和相减，即 L 和 R 拆不开

由此，状态应该修改

增加一维度 k 来限制 x 的左边界即可

另外还需要一个维度 p 代表当前位填的数是什么

所以状态： f[i][j][k][p]

依次枚举上一位的 p 来转移当前位即可

排列DP

• 定义：有一个 1 到 n 的排列， 求满足某个条件的排列有多少种

• 求 1 到 n 的排列中，逆序对数量是偶数个的排列的个数

定义状态：

初始化： f[1][0] = 1 （ 1 - 1 的排列形成0个逆序对的方案数为 1）

枚举方法： 把第 i 个数插入到的位置

优化方法：第二维度 j 只考虑奇偶即可，即 j 只能为 0 或 1

例题

• 对于一个排列，定义其“激动值”为序列中严格大于前面所有数的元素的个数。
  比如， {1,1,5,6,5} 的激动值为 3 。给定 n 个数 p_1,p_2, \cdots,p_n ，求这 n 个数的所有排列中，激动值不超过 k 的个数。 1≤k≤n≤200,\ 1≤p_i≤200

正着插入第 i 个数会影响到后面数
而倒着插入并不会影响到后面的数，所以选择倒着插入 i

所以定义状态： f[i][j] ， i 表示倒着从 n 排到了 i ， j 表示当前激动值

由于插入的 i 是已经插入的数里面的最小的一个，所以只有当 i 插入到最前面的时候 f[i][j] 才会 +1

• 有一个 1 到 n 的排列
• 求最长上升子序列长度不超过 2 的排列有多少个