zydp

解释

设表示前行，第行的状态为，且棋盘上已经放置个国王时的合法方案数。

对于编号为的状态，我们用二进制整数表示国王的放置情况，的某个二进制位为表示对应位置不放国王，为表示在对应位置上放置国王；用表示该状态的国王个数，即二进制数中的个数。例如，如下图所示的状态可用二进制数来表示（棋盘左边对应二进制低位），则有 $sit(j)=100101_{(2)}=37, sta(j)=3$ 。

设当前行的状态为，上一行的状态为，可以得到下面的状态转移方程： $f(i,j,l) = \sum f(i-1,x,l-sta(j))$ 。

设上一行的状态编号为，在保证当前行和上一行不冲突的前提下，枚举所有可能的进行转移，转移方程：

$f(i,j,l) = \sum f(i-1,x,l-sta(j))$

实现

参考代码

例题 2

[POI2004] PRZ

有个人需要过桥，第的人的重量为，过桥用时为 . 这些人过桥时会分成若干组，只有在某一组的所有人全部过桥后，其余的组才能过桥。桥最大承重为，问这些人全部过桥的最短时间。

$100\le W \le 400$ ， $1\le n\le 16$ ， $1\le t_i\le 50$ ， $10\le w_i\le 100$ .

解释

我们用表示所有人构成集合的一个子集，设表示中人的最长过桥时间，表示中所有人的总重量，表示中所有人全部过桥的最短时间，则：

$\begin{cases} f(\varnothing)=0,\ f(S)=\min\limits_{T\subseteq S;~w(T)\leq W}\left{t(T)+f(S\setminus T)\right}. \end{cases}$

需要注意的是这里不能直接枚举集合再判断是否为子集，而应使用子集枚举，从而使时间复杂度为 .

实现

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int W, n;
  cin >> W >> n;
  const int S = (1 << n) - 1;
  vector<int> ts(S + 1), ws(S + 1);
  for (int j = 0, t, w; j < n; ++j) {
    cin >> t >> w;
    for (int i = 0; i <= S; ++i)
      if (i & (1 << j)) {
        ts[i] = max(ts[i], t);
        ws[i] += w;
      }
  }
  vector<int> dp(S + 1, numeric_limits<int>::max() / 2);
  for (int i = 0; i <= S; ++i) {
    if (ws[i] <= W) dp[i] = ts[i];
    for (int j = i; j; j = i & (j - 1))
      if (ws[i ^ j] <= W) dp[i] = min(dp[i], dp[j] + ts[i ^ j]);
  }
  cout << dp[S] << '\n';
  return 0;
}

区间 DP

定义

区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。

令状态表示将下标位置到的所有元素合并能获得的价值的最大值，那么 $f(i,j)=\max{f(i,k)+f(k+1,j)+cost}$ ，为将这两组元素合并起来的价值。

性质

区间 DP 有以下特点：

合并：即将两个或多个部分进行整合，当然也可以反过来；

特征：能将问题分解为能两两合并的形式；

求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

解释

例题

「NOI1995」石子合并

题目大意：在一个环上有个数 $a_1,a_2,\dots,a_n$ ，进行次合并操作，每次操作将相邻的两堆合并成一堆，能获得新的一堆中的石子数量的和的得分。你需要最大化你的得分。

需要考虑不在环上，而在一条链上的情况。

令表示将区间内的所有石子合并到一起的最大得分。

写出 状态转移方程：![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7 "f(i,j)=\max{f(i,k)+f(k+1,j)+\sum_{t=i}^{j} a_t }~(i\le k)

令表示数组的前缀和，状态转移方程变形为 $f(i,j)=\max{f(i,k)+f(k+1,j)+sum_j-sum_{i-1} }$ 。

怎样进行状态转移

由于计算的值时需要知道所有和的值，而这两个中包含的元素的数量都小于，所以我们以作为 DP 的阶段。首先从小到大枚举，然后枚举的值，根据和用公式计算出的值，然后枚举，时间复杂度为

怎样处理环

题目中石子围成一个环，而不是一条链，怎么办呢？

方法一：由于石子围成一个环，我们可以枚举分开的位置，将这个环转化成一个链，由于要枚举次，最终的时间复杂度为。

方法二：我们将这条链延长两倍，变成 $2\times n$ 堆，其中第堆与第堆相同，用动态规划求解后，取 $f(1,n),f(2,n+1),\dots,f(n-1,2n-2)$ 中的最优值，即为最后的答案。时间复杂度。

实现

for (len = 2; len <= n; len++)
  for (i = 1; i <= 2 * n - 1 - len; i++) {
    int j = len + i - 1;
    for (k = i; k < j; k++)
      f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + sum[j] - sum[i - 1]);
  }

树形 DP

树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。

基础

以下面这道题为例，介绍一下树形 DP 的一般过程。

例题洛谷 P1352 没有上司的舞会

某大学有个职员，编号为 $1 \sim N$ 。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

我们设代表以为根的子树的最优解（第二维的值为 0 代表不参加舞会的情况，1 代表参加舞会的情况）。

对于每个状态，都存在两种决策（其中下面的都是的儿子）：

上司不参加舞会时，下属可以参加，也可以不参加，此时有 $f(i,0) = \sum\max {f(x,1),f(x,0)}$ ；
上司参加舞会时，下属都不会参加，此时有 $f(i,1) = \sum{f(x,0)} + a_i$ 。

我们可以通过 DFS，在返回上一层时更新当前结点的最优解。

| 1`` 2`` 3`` 4`` 5`` 6`` 7`` 8`` 9``10``11``12``13``14``15``16``17``18``19``20``21``22``23``24``25``26``27``28``29``30``31``32``33``34``35``36``37``38``39``40``41``42``43 |

#include <algorithm>
#include <cstdio>
using namespace std;

struct edge {
  int v, next;
} e[6005];

int head[6005], n, cnt, f[6005][2], ans, is_h[6005], vis[6005];

void addedge(int u, int v) {  // 建图
  e[++cnt].v = v;
  e[cnt].next = head[u];
  head[u] = cnt;
}

void calc(int k) {
  vis[k] = 1;
  for (int i = head[k]; i; i = e[i].next) {  // 枚举该结点的每个子结点
    if (vis[e[i].v]) continue;
    calc(e[i].v);
    f[k][1] += f[e[i].v][0];
    f[k][0] += max(f[e[i].v][0], f[e[i].v][1]);  // 转移方程
  }
  return;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &f[i][1]);
  for (int i = 1; i < n; i++) {
    int l, k;
    scanf("%d%d", &l, &k);
    is_h[l] = 1;
    addedge(k, l);
  }
  for (int i = 1; i <= n; i++)
    if (!is_h[i]) {  // 从根结点开始DFS
      calc(i);
      printf("%d", max(f[i][1], f[i][0]));
      return 0;
    }
}

习题

树上背包

树上的背包问题，简单来说就是背包问题与树形 DP 的结合。

例题洛谷 P2014 CTSC1997 选课

现在有门课程，第门课程的学分为，每门课程有零门或一门先修课，有先修课的课程需要先学完其先修课，才能学习该课程。

一位学生要学习门课程，求其能获得的最多学分数。

$n,m \leq 300$

每门课最多只有一门先修课的特点，与有根树中一个点最多只有一个父亲结点的特点类似。

因此可以想到根据这一性质建树，从而所有课程组成了一个森林的结构。为了方便起见，我们可以新增一门学分的课程（设这个课程的编号为），作为所有无先修课课程的先修课，这样我们就将森林变成了一棵以号课程为根的树。

我们设表示以号点为根的子树中，已经遍历了号点的前棵子树，选了门课程的最大学分。

转移的过程结合了树形 DP 和背包 DP 的特点，我们枚举点的每个子结点，同时枚举以为根的子树选了几门课程，将子树的结果合并到上。

记点的儿子个数为，以为根的子树大小为 $\textit{siz_x}$ ，可以写出下面的状态转移方程：

$f(u,i,j)=\max_{v,k \leq j,k \leq \textit{siz_v}} f(u,i-1,j-k)+f(v,s_v,k)$

注意上面状态转移方程中的几个限制条件，这些限制条件确保了一些无意义的状态不会被访问到。

的第二维可以很轻松地用滚动数组的方式省略掉，注意这时需要倒序枚举的值。

可以证明，该做法的时间复杂度为 ^[1](https://oiwiki.net/dp/tree/#fn:note1)^。

参考代码

</details>

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int f[305][305], s[305], n, m;
vector<int> e[305];int dfs(int u) {
int p = 1;
f[u][1] = s[u];
for (auto v : e[u]) {
int siz = dfs(v);
// 注意下面两重循环的上界和下界
// 只考虑已经合并过的子树，以及选的课程数超过 m+1 的状态没有意义
for (int i = min(p, m + 1); i; i--)
for (int j = 1; j <= siz && i + j <= m + 1; j++)
f[u][i + j] = max(f[u][i + j], f[u][i] + f[v][j]);  // 转移方程
p += siz;
}
return p;
}int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
int k;
scanf("%d%d", &k, &s[i]);
e[k].push_back(i);
}
dfs(0);
printf("%d", f[0][m + 1]);
return 0;
}

习题

换根 DP

树形 DP 中的换根 DP 问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响。

通常需要两次 DFS，第一次 DFS 预处理诸如深度，点权和之类的信息，在第二次 DFS 开始运行换根动态规划。

接下来以一些例题来带大家熟悉这个内容。

例题 [POI2008]STA-Station

给定一个个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。

不妨令为当前结点，为当前结点的子结点。首先需要用来表示以为根的子树中的结点个数，并且有 $s_u=1+\sum s_v$ 。显然需要一次 DFS 来计算所有的，这次的 DFS 就是预处理，我们得到了以某个结点为根时其子树中的结点总数。

考虑状态转移，这里就是体现＂换根＂的地方了。令为以为根时，所有结点的深度之和。

$f_v\leftarrow f_u$ 可以体现换根，即以为根转移到以为根。显然在换根的转移过程中，以为根或以为根会导致其子树中的结点的深度产生改变。具体表现为：

所有在的子树上的结点深度都减少了一，那么总深度和就减少了；
所有不在的子树上的结点深度都增加了一，那么总深度和就增加了；

根据这两个条件就可以推出状态转移方程 $f_v = f_u - s_v + n - s_v=f_u + n - 2 \times s_v$ 。

于是在第二次 DFS 遍历整棵树并状态转移 $f_v=f_u + n - 2 \times s_v$ ，那么就能求出以每个结点为根时的深度和了。最后只需要遍历一次所有根结点深度和就可以求出答案。

#include <bits/stdc++.h>
using namespace std;

int head[1000010 << 1], tot;
long long n, sz[1000010], dep[1000010];
long long f[1000010];

struct node {
  int to, next;
} e[1000010 << 1];

void add(int u, int v) {  // 建图
  e[++tot] = {v, head[u]};
  head[u] = tot;
}

void dfs(int u, int fa) {  // 预处理dfs
  sz[u] = 1;
  dep[u] = dep[fa] + 1;
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (v != fa) {
      dfs(v, u);
      sz[u] += sz[v];
    }
  }
}

void get_ans(int u, int fa) {  // 第二次dfs换根dp
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (v != fa) {
      f[v] = f[u] - sz[v] * 2 + n;
      get_ans(v, u);
    }
  }
}

int main() {
  scanf("%lld", &n);
  int u, v;
  for (int i = 1; i <= n - 1; i++) {
    scanf("%d%d", &u, &v);
    add(u, v);
    add(v, u);
  }
  dfs(1, 1);
  for (int i = 1; i <= n; i++) f[1] += dep[i];
  get_ans(1, 1);
  long long int ans = -1;
  int id;
  for (int i = 1; i <= n; i++) {  // 统计答案
    if (f[i] > ans) {
      ans = f[i];
      id = i;
    }
  }
  printf("%d\n", id);
  return 0;
}

计数 DP

计数 DP 是一种利用类似 DP 的记忆化搜索方法（与在狭义上的 DP，即最优化问题有一定区别），用于解决计数（以及求和）问题。

基础

基本思想

计数问题一般指求一个集合的大小，在 OI 中，的大小有时会达到 $\Theta(n^n)$ 甚至 $\Theta(2^{n!})$ 的级别（当然，一般会对某一个固定的数取模），其中是问题规模，所以我们不能逐一求出的元素。

如果我们能够将分成若干无交的子集，那么的元素个数就等于这些部分的元素个数的和。如果这些子集的计数恰好与原问题类似，那么我们就可以通过类似动态规划的方法来解决。

例题

给定一个正整数，求有多少个把划分成个正整数的和的方案，位置调换视为不同的划分方案。

需集合 $S_{n,k}$ 为形如 $(a_1, \dots, a_k)$ 的正整数组组成的集合，其中 $a_1 + \dots + a_k = n$ 。如果固定，则有如下推导：因为 $a_1 + a_2 + \dots + a_{k-1} + a_k = n$ ，所以 $a_1 + a_2 + \dots + a_{k-1} = n - a_k$ 。根据 $S_{n,k}$ 的定义， $(a_1, a_2, \dots, a_{k-1}) \in S_{n - a_k, k - 1}$ 。

由于 $a_1, a_2, \dots, a_k$ 是正整数，所以的取值范围是 $[1, n - k + 1] \cap \mathbb Z$ 。因此， $S_{n,k}$ 可以按照被划分，分成个子集，其中当时，这个子集为：

${(L, i) \mid L \in S_{n-i,k-1}}.$

这个子集的元素个数显然等于 $S_{n-i,k-1}$ ，由于的不同，这些子集两两无交。所以：

$|S_{n,k}| = \sum_{i=1}^{n-k+1} |S_{n-i,k-1}|.$

这样我们就可以使用类似 DP 的方法处理它：设 $f_{n,k}$ 为 $|S_{n,k}|$ ，则有状态转移方程：

$f_{n,k} = \sum_{i=1}^{n-k+1} f_{n-i,k-1}.$

这样就可以使用 DP 的方法求解了。

与最优化 DP 的异同

可以发现，计数 DP 和最优化 DP 都是在一个范围 $\Omega$ 内求一个值（大小值、最优值），这个值通过将 $\Omega$ 中的所有元素做一次处理，再对处理值做一次整合得到。

例如，对于 0-1 背包问题， $\Omega$ 中的元素为背包内的所有物品组成的集合，对于 $\Omega$ 中的一个方案，我们对做一次处理，处理得到的结果为中物品的总价值，对所有得到的处理值，我们取最大值，得到问题的答案。

对于计数问题， $\Omega$ 中的元素为要计算元素个数的集合，它的处理是把所有的中元素变为，然后将这些通过加法的方式汇总起来，因为每一个中元素都对应一个，所以这样得到的值就是中元素个数。

当汇总操作为最大/最小值时，我们可以将 $\Omega$ 分成任意若干个部分，只需这些部分的并为 $\Omega$ 即可，无需无交的条件。而计数问题由于不满足这个条件，所以我们需要将 $\Omega$ 分成若干个部分，这些部分两两无交，这就是与最优化 DP 的区别。

例题

给定一个正整数，求有多少个把划分成任意多个正整数的和的方案，位置调换视为相同的划分方案。

解法 1

需要计算的集合的元素为满足其和为的正整数多重集。但是这样显然不好推。

若一个多重集只包含 $\le M$ 的正整数，且中所有元素的和为，则称 $T \in S_{n, M}$ 。考虑出现的个数。可能为 $k \in \left[0, \left\lfloor \dfrac nM \right\rfloor\right] \cap \mathbb Z$ 。于是它可以被转移到 $S_{n - kM, M - 1}$ 。求和一下即可。复杂度是 $\Theta(n^2 \log n)$ （ $\log$ 来自于的范围导致的调和级数）。

但是这样还不够优秀。考虑下面所示的一个例子：

$\begin{aligned} f_{8, 3} &= {\color{red}f_{8, 2} + f_{5, 2} + f_{2, 2}} \ f_{9, 3} &= {\color{blue}f_{9, 2} + f_{6, 2} + f_{3, 2} + f_{0, 2}} \ f_{10, 3} &= {\color{green}f_{10, 2} + f_{7, 2} + f_{4, 2} + f_{1, 2}}\ f_{11, 3} &= f_{11, 2} + {\color{red}f_{8, 2} + f_{5, 2} + f_{2, 2}}\ f_{12, 3} &= f_{12, 2} + {\color{blue}f_{9, 2} + f_{6, 2} + f_{3, 2} + f_{0, 2}}\ f_{13, 3} &= f_{13, 2} + {\color{green}f_{10, 2} + f_{7, 2} + f_{4, 2} + f_{1, 2}}\ \end{aligned}$

等量代换得 $f_{11, 3} = f_{11, 2} + f_{8, 3}$ ， $f_{12, 3} = f_{12, 2} + f_{9, 3}$ ， $f_{13, 3} = f_{13, 2} + f_{10, 3}$ 。同理我们可以得到一个通用的状态转移方程：

$f_{n, M} = f_{n, M - 1} + \begin{cases} f_{n - M, M} & n \ge M, \ 0 & \text{otherwise}. \end{cases}$

此时，时间复杂度为 $\Theta(n^2)$ 。

解法 2

考虑到某一个正整数组成的多重集必然可以通过「将中每一个元素自增」、「在中加一个值为的元素」两个操作得到，并且不同的操作序列得到的结果是不同的。

这样对的转移可以变为对操作序列的转移。考虑将划分成个数的操作序列（所有的这些操作序列记作 $B_{n,m}$ ）中的最后一次操作，如果是操作，那么不会增加数，但是 $\sum T$ 增加了。为了使最终的 $\sum T = n$ ，原来的（记作）的和需要为。所以 $B_{n,m} \to B_{n-m,m}$ ；如果是操作，那么会增加一个数， $\sum T$ 增加了。所以 $B_{n,m} \to B_{n-1,m-1}$ 。

这样做的时间复杂度依旧是 $\Theta(n^2)$ 。

解法 3

考虑将分为大于 $\sqrt n$ 的部分和小于等于 $\sqrt n$ 的部分。可以使用解法 1 求出，而的数量可以通过略微修改解法 2 求出：考虑将两个操作变为「将中每一个元素自增」、「在中加一个值为 $\lfloor \sqrt n \rfloor + 1$ 的元素」。容易列出状态转移方程。

将拆为和两部分。枚举其中一个即可得出另一个。将满足 $\sum T_1 = A$ 的个数和 $\sum T_2 = B$ 的个数求出，乘起来，对所有的求和便是最终结果。

由于在计算个数的过程中， $M \le \sqrt n$ ，所以我们利用解法 1 计算的时间复杂度为 $\Theta(n^{3/2})$ 。同样地，由于在计算个数的过程中， $|T_2| \le \dfrac{\sum T_2}{\sqrt n} \le \dfrac{n}{\sqrt n} = \sqrt n$ ，所以我们利用解法 2 计算的时间复杂度也是 $\Theta(n^{3/2})$ 。所以总时间复杂度为 $\Theta(n^{3/2})$ 。

数位 DP

本页面将简要介绍数位 DP。

引入

数位是指把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制。

数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：

要求统计满足一定条件的数的数量（即，最终目的为计数）；
这些条件经过转化后可以使用「数位」的思想去理解和判断；
输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
上界很大（比如 $10^{18}$ ），暴力枚举验证会超时。

数位 DP 的基本原理：

考虑人类计数的方式，最朴素的计数就是从小到大开始依次加一。但我们发现对于位数比较多的数，这样的过程中有许多重复的部分。例如，从 7000 数到 7999、从 8000 数到 8999、和从 9000 数到 9999 的过程非常相似，它们都是后三位从 000 变到 999，不一样的地方只有千位这一位，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推或 DP 的方式进行状态转移。

数位 DP 中通常会利用常规计数问题技巧，比如把一个区间内的答案拆成两部分相减（即 $\mathit{ans}_{[l, r]} = \mathit{ans}_{[0, r]}-\mathit{ans}_{[0, l - 1]}$ ）

那么有了通用答案数组，接下来就是统计答案。统计答案可以选择记忆化搜索，也可以选择循环迭代递推。为了不重不漏地统计所有不超过上限的答案，要从高到低枚举每一位，再考虑每一位都可以填哪些数字，最后利用通用答案数组统计答案。

接下来我们具体看几道题目。

例题一

例 1 Luogu P2602 数字计数

题目大意：给定两个正整数，求在中的所有整数中，每个数码（digit）各出现了多少次。

方法一

解释

发现对于满 $\mathit{i}$ 位的数，所有数字出现的次数都是相同的，故设数组 $\mathit{dp}_i$ 为满位的数中每个数字出现的次数，此时暂时不处理前导零。则有 $\mathit{dp}_i=10 \times \mathit{dp}_{i−1}+10^{i−1}$ ，这两部分前一个是来自前位数字的贡献，后一个是来自第位的数字的贡献。

有了 $\mathit{dp}$ 数组，我们来考虑如何统计答案。将上界按位分开，从高到低枚举，不贴着上界时，后面可以随便取值。贴着上界时，后面就只能取到上界，分两部分分别计算贡献。最后考虑下前导零，第位为前导时，此时到 $\mathit{i-1}$ 位也都是，也就是多算了将位填满的答案，需要额外减去。

实现

参考代码

| 1`` 2`` 3`` 4`` 5`` 6`` 7`` 8`` 9``10``11``12``13``14``15``16``17``18``19``20``21``22``23``24``25``26``27``28``29``30``31

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
typedef long long ll;
ll l, r, dp[N], mi[N];
ll ans1[N], ans2[N];
int a[N];

void solve(ll n, ll *ans) {
  ll tmp = n;
  int len = 0;
  while (n) a[++len] = n % 10, n /= 10;
  for (int i = len; i >= 1; --i) {
    for (int j = 0; j < 10; j++) ans[j] += dp[i - 1] * a[i];
    for (int j = 0; j < a[i]; j++) ans[j] += mi[i - 1];
    tmp -= mi[i - 1] * a[i], ans[a[i]] += tmp + 1;
    ans[0] -= mi[i - 1];
  }
}

int main() {
  scanf("%lld%lld", &l, &r);
  mi[0] = 1ll;
  for (int i = 1; i <= 13; ++i) {
    dp[i] = dp[i - 1] * 10 + mi[i - 1];
    mi[i] = 10ll * mi[i - 1];
  }
  solve(r, ans1), solve(l - 1, ans2);
  for (int i = 0; i < 10; ++i) printf("%lld ", ans1[i] - ans2[i]);
  return 0;
}

方法二

解释

此题也可以使用记忆化搜索。 $\mathit{dp}_i$ 表示不贴上限、无前导零时，位数为的答案。

详见代码注释

过程

参考代码

| 1`` 2`` 3`` 4`` 5`` 6`` 7`` 8`` 9``10``11``12``13``14``15``16``17``18``19``20``21``22``23``24``25``26``27``28``29``30``31``32``33``34``35``36``37``38``39``40``41``42``43``44``45``46``47``48``49``50``51``52``53

#include <cstdio>  //code by Alphnia
#include <cstring>
#include <iostream>
using namespace std;
#define N 50005
#define ll long long
ll a, b;
ll f[15], ksm[15], p[15], now[15];

ll dfs(int u, int x, bool f0,
       bool lim) {  // u 表示位数，f0 是否有前导零，lim 是否都贴在上限上
  if (!u) {
    if (f0) f0 = 0;
    return 0;
  }
  if (!lim && !f0 && (~f[u])) return f[u];
  ll cnt = 0;
  int lst = lim ? p[u] : 9;
  for (int i = 0; i <= lst; i++) {  // 枚举这位要填的数字
    if (f0 && i == 0)
      cnt += dfs(u - 1, x, 1, lim && i == lst);  // 处理前导零
    else if (i == x && lim && i == lst)
      cnt += now[u - 1] + 1 +
             dfs(u - 1, x, 0,
                 lim && i == lst);  // 此时枚举的前几位都贴在给定的上限上。
    else if (i == x)
      cnt += ksm[u - 1] + dfs(u - 1, x, 0, lim && i == lst);
    else
      cnt += dfs(u - 1, x, 0, lim && i == lst);
  }
  if ((!lim) && (!f0)) f[u] = cnt;  // 只有不贴着上限和没有前导零才能记忆
  return cnt;
}

ll gans(ll d, int dig) {
  int len = 0;
  memset(f, -1, sizeof(f));
  while (d) {
    p[++len] = d % 10;
    d /= 10;
    now[len] = now[len - 1] + p[len] * ksm[len - 1];
  }
  return dfs(len, dig, 1, 1);
}

int main() {
  scanf("%lld%lld", &a, &b);
  ksm[0] = 1;
  for (int i = 1; i <= 12; i++) ksm[i] = ksm[i - 1] * 10ll;
  for (int i = 0; i < 9; i++) printf("%lld ", gans(b, i) - gans(a - 1, i));
  printf("%lld\n", gans(b, 9) - gans(a - 1, 9));
  return 0;
}

| | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |

例题二

例 2 HDU 2089 不要 62

题面大意：统计一个区间内数位上不能有 4 也不能有连续的 62 的数有多少。

解释

没有 4 的话在枚举的时候判断一下，不枚举 4 就可以保证状态合法了，所以这个约束没有记忆化的必要，而对于 62 的话，涉及到两位，当前一位是 6 或者不是 6 这两种不同情况计数是不相同的，所以要用状态来记录不同的方案数。 $\mathit{dp}_{\mathit{pos},\mathit{sta}}$ 表示当前第 $\mathit{pos}$ 位，前一位是否是 6 的状态，这里 $\mathit{sta}$ 只需要取 0 和 1 两种状态就可以了，不是 6 的情况可视为同种，不会影响计数。

实现

参考代码

| 1`` 2`` 3`` 4`` 5`` 6`` 7`` 8`` 9``10``11``12``13``14``15``16``17``18``19``20``21``22``23``24``25``26``27``28``29``30``31``32``33``34``35``36``37``38``39``40``41``42``43``44``45``46``47

#include <cstdio>  //code by Alphnia
#include <cstring>
#include <iostream>
using namespace std;
int x, y, dp[15][3], p[50];

int pre() {
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int i = 1; i <= 10; i++) {
    dp[i][0] = dp[i - 1][0] * 9 - dp[i - 1][1];
    dp[i][1] = dp[i - 1][0];
    dp[i][2] = dp[i - 1][2] * 10 + dp[i - 1][1] + dp[i - 1][0];
  }
}

int cal(int x) {
  int cnt = 0, ans = 0, tmp = x;
  while (x) {
    p[++cnt] = x % 10;
    x /= 10;
  }
  bool flag = 0;
  p[cnt + 1] = 0;
  for (int i = cnt; i; i--) {  // 从高到低枚举数位
    ans += p[i] * dp[i - 1][2];
    if (flag)
      ans += p[i] * dp[i - 1][0];
    else {
      if (p[i] > 4) ans += dp[i - 1][0];
      if (p[i] > 6) ans += dp[i - 1][1];
      if (p[i] > 2 && p[i + 1] == 6) ans += dp[i][1];
      if (p[i] == 4 || (p[i] == 2 && p[i + 1] == 6)) flag = 1;
    }
  }
  return tmp - ans;
}

int main() {
  pre();
  while (~scanf("%d%d", &x, &y)) {
    if (!x && !y) break;
    x = min(x, y), y = max(x, y);
    printf("%d\n", cal(y + 1) - cal(x));
  }
  return 0;
}

例题三

例 3 SCOI2009 windy 数

题目大意：给定一个区间，求其中满足条件 不含前导且相邻两个数字相差至少为 的数字个数。

解释

首先我们将问题转化成更加简单的形式。设 $\mathit{ans}_i$ 表示在区间中满足条件的数的数量，那么所求的答案就是 $\mathit{ans}_r-\mathit{ans}_{l-1}$ 。

对于一个小于的数，它从高到低肯定出现某一位，使得这一位上的数值小于这一位上对应的数值。而之前的所有位都和上的位相等。

有了这个性质，我们可以定义表示当前将要考虑的是从高到低的第位，当前该前缀的状态为且前缀和当前求解的数字的大小关系是（表示等于，表示小于）时的数字个数。在本题中，这个前缀的状态就是上一位的值，因为当前将要确定的位不能取哪些数只和上一位有关。在其他题目中，这个值可以是：前缀的数字和，前缀所有数字的 $\gcd$ ，该前缀取模某个数的余数，也有两种或多种合用的情况。

写出 状态转移方程： $f(i,st,op)=\sum_{k=1}^{\mathit{maxx}} f(i+1,k,op=1~ \operatorname{and}~ k=\mathit{maxx} )\quad (|\mathit{st}-k|\ge 2)$

这里的就是当前枚举的下一位的值，而 $\mathit{maxx}$ 就是当前能取到的最高位。因为如果 $\mathit{op}=1$ ，那么你在这一位上取的值一定不能大于求解的数字上该位的值，否则则没有限制。

我们发现，尽管前缀所选择的状态不同，而的三个参数相同，答案就是一样的。为了防止这个答案被计算多次，可以使用记忆化搜索的方式实现。

实现

int dfs(int x, int st, int op)  // op=1 =;op=0 <
{
  if (!x) return 1;
  if (!op && ~f[x][st]) return f[x][st];
  int maxx = op ? dim[x] : 9, ret = 0;
  for (int i = 0; i <= maxx; i++) {
    if (abs(st - i) < 2) continue;
    if (st == 11 && i == 0)
      ret += dfs(x - 1, 11, op & (i == maxx));
    else
      ret += dfs(x - 1, i, op & (i == maxx));
  }
  if (!op) f[x][st] = ret;
  return ret;
}

int solve(int x) {
  memset(f, -1, sizeof f);
  dim.clear();
  dim.push_back(-1);
  int t = x;
  while (x) {
    dim.push_back(x % 10);
    x /= 10;
  }
  return dfs(dim.size() - 1, 11, 1);
}

</details>

例题四

例 4.SPOJMYQ10

题面大意：假如手写下之间所有整数，会有多少数看起来和在镜子里看起来一模一样？（ $n,m<10^{44}, T<10^5$ ）

解释

注：由于这里考虑到的镜像，只有的镜像是自己本身。所以，这里的「一模一样」并不是传统意义上的回文串，而是只含有的回文串。

首先，在数位 DP 过程中，显然只有能被选中。

其次，由于数值超过 long long 范围，所以不再适用（高精度比较繁琐），而是需要对是否合法进行判断，得出： $[n,m]=[1,m]-[1,n]+\mathrm{check}(n)$ 。

镜像解决了，如何判断回文？

我们需要用一个小数组记录一下之前的值。在未超过一半的长度时，只要不超上限就行；在超过一半的长度时，还需要判断是否和与之「镜面对称」的位相等。

需要额外注意的是，这道题的记忆化部分，不能用 memset，否则会导致超时。

实现

参考代码

| 1`` 2`` 3`` 4`` 5`` 6`` 7`` 8`` 9``10``11``12``13``14``15``16``17``18``19``20``21``22``23``24``25``26``27``28``29``30``31``32``33``34``35``36``37``38``39``40``41``42

int check(char cc[]) {  // n 的特判
  int strc = strlen(cc);
  for (int i = 0; i < strc; ++i) {
    if (!(cc[i] == cc[strc - i - 1] &&
          (cc[i] == '1' || cc[i] == '8' || cc[i] == '0')))
      return 0ll;
  }
  return 1ll;
}

// now: 当前位, eff: 有效位, fulc: 是否全顶格, ful0: 是否全0
int dfs(int now, int eff, bool ful0, bool fulc) {
  if (now == 0) return 1ll;
  if (!fulc && f[now][eff][ful0] != -1)  // 记忆化
    return f[now][eff][ful0];

  int res = 0, maxk = fulc ? dig[now] : 9;
  for (int i = 0; i <= maxk; ++i) {
    if (i != 0 && i != 1 && i != 8) continue;
    b[now] = i;
    if (ful0 && i == 0)  // 全前导 0
      res += dfs(now - 1, eff - 1, 1, 0);
    else if (now > eff / 2)                                  // 未过半程
      res += dfs(now - 1, eff, 0, fulc && (dig[now] == i));  // 已过半程
    else if (b[now] == b[eff - now + 1])
      res += dfs(now - 1, eff, 0, fulc && (dig[now] == i));
  }
  if (!fulc) f[now][eff][ful0] = res;
  return res;
}

char cc1[100], cc2[100];
int strc, ansm, ansn;

int get(char cc[]) {  // 处理封装
  strc = strlen(cc);
  for (int i = 0; i < strc; ++i) dig[strc - i] = cc[i] - '0';
  return dfs(strc, strc, 1, 1);
}

scanf("%s%s", cc1, cc2);
printf("%lld\n", get(cc2) - get(cc1) + check(cc1));

| ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |

例题五

例 5.P3311 数数

题面：我们称一个正整数是幸运数，当且仅当它的十进制表示中不包含数字串集合中任意一个元素作为其子串。例如当时，是幸运数，、、不是幸运数。给定和，计算不大于的幸运数个数。答案对取模。

，，， $1 \leq n<10^{1201}，1 \leq m \leq 100，1 \leq \sum_{i = 1}^m |s_i| \leq 1500，\min_{i = 1}^m |s_i| \geq 1$ ，其中表示字符串的长度。没有前导，但是可能有前导。

解释

阅读题面发现，如果将数字看成字符串，那么这就是需要完成一个多模匹配，自然而然就想到 AC 自动机。普通数位 DP 中，先从高到低枚举数位，再枚举每一位都填什么，在这道题中，我们也就自然地转化为枚举已经填好的位数，再枚举此时停在 AC 自动机上的哪个节点，然后从当前节点转移到它在 AC 自动机上的子节点。

设表示当前从高到低已经填了位（即在 AC 自动机上走过了条边），此时停在标号为的节点上，当前是否正好贴着上界。

至于题目中的「不包含」条件，只需在 AC 自动机上给每个模式串的结尾节点都打上标记，DP 过程中一旦遇上这些结尾节点就跳过即可。

转移很好想，详见代码主函数部分。

实现

参考代码

#include <bits/stdc++.h>  //code by Alphnia
using namespace std;
#define N 1505
#define ll long long
#define mod 1000000007
int n, m;
char s[N], c[N];
int ch[N][10], fail[N], ed[N], tot, len;

void insert() {
  int now = 0;
  int L = strlen(s);
  for (int i = 0; i < L; ++i) {
    if (!ch[now][s[i] - '0']) ch[now][s[i] - '0'] = ++tot;
    now = ch[now][s[i] - '0'];
  }
  ed[now] = 1;
}

queue<int> q;

void build() {
  for (int i = 0; i < 10; ++i)
    if (ch[0][i]) q.push(ch[0][i]);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 10; ++i) {
      if (ch[u][i]) {
        fail[ch[u][i]] = ch[fail[u]][i], q.push(ch[u][i]),
        ed[ch[u][i]] |= ed[fail[ch[u][i]]];
      } else
        ch[u][i] = ch[fail[u]][i];
    }
  }
  ch[0][0] = 0;
}

ll f[N][N][2], ans;

void add(ll &x, ll y) { x = (x + y) % mod; }

int main() {
  scanf("%s", c);
  n = strlen(c);
  scanf("%d", &m);
  for (int i = 1; i <= m; ++i) scanf("%s", s), insert();
  build();
  f[0][0][1] = 1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= tot; ++j) {
      if (ed[j]) continue;
      for (int k = 0; k < 10; ++k) {
        if (ed[ch[j][k]]) continue;
        add(f[i + 1][ch[j][k]][0], f[i][j][0]);
        if (k < c[i] - '0') add(f[i + 1][ch[j][k]][0], f[i][j][1]);
        if (k == c[i] - '0') add(f[i + 1][ch[j][k]][1], f[i][j][1]);
      }
    }
  }
  for (int j = 0; j <= tot; ++j) {
    if (ed[j]) continue;
    add(ans, f[n][j][0]);
    add(ans, f[n][j][1]);
  }
  printf("%lld\n", ans - 1);
  return 0;
}

此题可以很好地帮助理解数位 DP 的原理。

1 ↩︎

dp

zydp

解释

实现

例题 2

解释

实现

区间 DP

定义

性质

解释

例题

怎样进行状态转移

怎样处理环

实现

树形 DP

基础

习题

树上背包

习题

换根 DP

计数 DP

基础

基本思想

例题

与最优化 DP 的异同

例题

解法 1

解法 2

解法 3

数位 DP

引入

例题一

方法一

解释

实现

方法二

解释

过程

例题二

解释

实现

例题三

解释

实现

例题四

解释

实现

例题五

解释

实现

Status

Development

Support

Don't have an account?

SIGN IN