天天看点
返回

动态规划 | 数位 DP

动态规划 | 数位 DP

Luogu Wisdom Engine！Uh！

章零 · 序言

在我痛斥全给我推 DP 的 Luogu Wisdom Engine 和 GP2 Engine 一样令人 Uh 的时候，还是要看一看它到底给我推的什么题的。

于是昨天点开了 P2602 数字计数 [ZJOI2010]，一看显然是个数位 DP，但是我只是单纯的知道数位 DP，之前相关的题目也就只做过 Windy 数，于是决定学一下。

然后发现数位 DP 能套模板的题占多数，于是昨天下午 + 晚上做了好多数位 DP 题的样子，那么就来写一点东西罢（

章一 · 初见

那么什么是数位 DP 呢（

节一 · 简介

先放一下 OI-Wiki 上的数位介绍：

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

因为是小学知识所以就不多做解释。

那么数位和 DP 是什么我们都知道了，那么数位 DP 就是针对一些可以用数位的思想去解的题目，而这些题目通常会有非常明显的特征。

节二 · 题目特征

一般来说数位 DP 的题目有如下特征：

  1. 题目所求和数位相关或是转化后和数位相关，比如求一个数每一位的和；
  2. 一般是一个计数问题；
  3. 数据范围很大，所统计的答案已经与数据大小无关；
  4. 一般输入时给出的是一个区间。

简单来说就是，在区间 \([l,r]\) 中统计符合条件 \(P(i)\) 的数 \(i\) 的个数，一般 \(P(i)\) 和 \(i\) 的大小无关，而与 \(i\) 的数位组成有关。

既然和 \(i\) 的大小一般无关了，所以数位 DP 的复杂度就和 \(i\) 的大小关系不大了。

章二 · 模板

众所周知数位 DP 的模板是非常好套的，于是先来讲一讲模板罢。

当然好套只是其中一个原因，之所以先讲，是觉得先看完了模板框架和状态设计之后，更容易理解数位 DP 的过程。

节一 · 设计状态

我这里用记忆化搜索的形式来转移状态，这样的好处是我们的思维量更少，可以在 \(DFS\) 函数里维护更多的信息。

当然模板也更好套，更好背

下面的参数不懂可以先不用着急，下面节二会稍作分析。

条一 · DFS 函数

那么我们先来看一看 \(DFS\) 中都需要什么参数：

  1. \(\texttt{lead}\)：前导 \(0\) 的状态；
  2. \(\texttt{limit}\)：当前位置做多取值的有没有被限制；
  3. \(\texttt{pos}\)：当前的状态在原数中的位置；
  4. \(\texttt{st}\)：当前状态的答案；
  5. \(\texttt{pre}\)：上一位数字。
  6. \(\cdots\)

当然以上参数不一定每个题都需要，视题目而定即可。

当然你记录的东西多了一般也不会错

条二 · DP 数组

下文中的 DP 数组我都用 \(f(i,j,\cdots)\) 来表示。

一般来说我们要在 DP 数组中记录当前状态在原数中的位置 \(\texttt{pos}\) 和当前状态的答案 \(st\)，也就是说，对于简单的数位 DP，方程的样子一般都是 \(f(\texttt{pos},\texttt{st})\)。

当然根据题目的不同还有可能会往里面加一些其他的东西。

节二 · 参数分析

前面所说的参数可能初见会不懂，于是下面来稍作分析。

下文中若无特殊说明，\(a_{pos}\) 均表示原数第 \(pos\) 位的数。

条一 · lead

这个参数的存在是为了我们要从最高位开始搜时避免一些不必要的错误。

下面来举个例子：

求 \([l,r]\) 中有任意相邻两位相同的数字。

当 \(l=1,r=10000\) 时，显然 \(11,111,444,555,1111,4444\) 都是符合题意的数字。

但是我们搜索时记录出来的上列数字是这样的：\(00011,00111,00444,00555,01111,04444\)，显然有了前导 \(0\) 之后这些数字都不满足题意了，于是我们要把前导 \(0\) 的影响去掉。

这个标记的意义如下：

  1. \(\texttt{lead} = 0 \to DFS(\texttt{pos+1} \ \operatorname{or}\ \texttt{pos-1},\texttt{newst},\cdots)\)
  2. \(\texttt{lead} = 1 \begin{cases} a_{pos} = 0 &\to DFS(\texttt{pos+1} \ \operatorname{or}\ \texttt{pos-1},\texttt{st},\cdots) \\ a_{pos} \ne 0 &\to DFS(\texttt{pos+1} \ \operatorname{or}\ \texttt{pos-1},\texttt{newst},\cdots)\end{cases}\)

但是显然当我们所统计的东西和上一位是否为 \(0\) 无关的时候，这个参数也可以不用记录（比如问一个数的组成）。

条二 · limit

这个参数如果用相对严谨的形式去一句话定义的话会很绕，但是举个例子会非常有助于理解。

从范围 \([0,114514]\) 中找符合条件 \(P(i)\) 的数 \(i\)。

如果我们当前搜索到的数字的最高位为 \(1\)，那么显然我们次高位搜索的范围会被限制为 \([0,1]\)。

同理，当我们搜索到第 \(i\) 位的时候，若第 \(i-1\) 位达到了其限制，那么当前位置的搜索范围就由 \([0,9]\) 被限制到了 \([0,a_{pos}]\)。

为了区分当前位置有没有被限制，我们加入了参数 \(\texttt{limit}\)。

这个参数意义如下：

我们设 \(i\) 为我们在当前位上搜索到了 \(i\)，那么显然 \(i\in[0,9] \operatorname{or} i\in[0,a_pos]\)，为了方便，下面统一将可搜的数的最大值设为 \(up\)。

在这里 \(DFS\) 函数第二个参数为 \(\texttt{limit}\)。

  1. \(\texttt{limit} = 0 \to DFS(\texttt{pos+1} \ \operatorname{or}\ \texttt{pos-1},0,\cdots)\)
  2. \(\texttt{limit} = 1 \begin{cases} i < up &\to DFS(\texttt{pos+1} \ \operatorname{or}\ \texttt{pos-1},0,\cdots) \\ i = up &\to DFS(\texttt{pos+1} \ \operatorname{or}\ \texttt{pos-1},1,\cdots)\end{cases}\)

节三 · DP 数组

使用记忆化的原因很简单：数位 DP 过程中存在大量的重复状态，采取记忆化就可以有效的降低复杂度。

但是有时候一些状态并不能记录，也就是当前状态存在限制的时候不能取用之前的状态或将本次 DFS 结果存储在 DP 数组中。

一般来说即为 \(\texttt{limit} = 1\) 时显然不能取用和存储。

节四 · Code

前面对一些参数稍作分析之后，我们来上一份模板代码。

不过在上模板代码之前，先献上我的垃圾缺省源。

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cstring>
#define Heriko return
#define Deltana 0
#define Romanno 1
#define S signed
#define LL long long
#define R register
#define I inline
#define CI const int
#define mst(a, b) memset(a, b, sizeof(a))
#define ON std::ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

template<typename J>
I void fr(J &x)
{
static short f(1);
char c=getchar();
x=0;
while(c<'0' or c>'9')
    {
if(c=='-') f=-1;
c=getchar();
    }
while (c>='0' and c<='9') 
    {
x=(x<<3)+(x<<1)+(c^=48);
c=getchar();
    }
x*=f;
}

template<typename J>
I void fw(J x,bool k)
{
x<0?x=-x,putchar('-'):1;
static short stak[35],top(0);
do
    {
stak[top++]=x%10;
x/=10;
    }
while(x);
while(top) putchar(stak[--top]+'0');
k?puts(""):putchar(' ');
}

然后就是模板代码。

LL DFS(bool limit,int st,int pos,...)
{
if(!pos and ...) Heriko st;
if(!limit and f[pos][st]...[...]!=-1 and ...) Heriko f[pos][st]...[...];
int res(0),up(limit?a[pos]:9);
for(R int i(0);i<=up;++i) res+=DFS(...);
if(!limit and ...) f[pos][st]...[...]=res;
Heriko res;
}

I LL DP(LL x)
{
mst(f,-1);
int len(0);
while(x) a[++len]=x%10,x/=10;
Heriko DFS(1,0,len);
}

S main()
{
fr(l),fr(r);
fw((DP(r)-DP(l-1)+MOD)%MOD,1);
Heriko Deltana;
}

章三 · 例题

如果你能看懂模板，那么下面这道题你能很容易的切掉。

​​LOJ | #10169.数字计数​​

​​洛谷 | P2602 数字计数 [ZJOI2007]​​ [提高+/省选-]

给定两个正整数 \(a\) 和 \(b\)，求在 \([a,b]\) 中的所有整数中，每个数码(digit)各出现了多少次。

节一 · 思路

是一道数位 DP 的板子题，正好遇上洛谷日爆（

采用模板化的 DFS 做法，定义 \(f\) 数组如下 \(f(i,j)\) 表示是从高到低第 \(i\) 位，\(j\) 则是数字出现次数。

DFS 函数为 \(DFS(pos,num,ans,lead,limit)\)，参数分别表示：从高到低第几位，要求哪个数出现的次数，当前出现次数，前导零的状态，当前位置上限的状态。

节二 · Code 

CI MXX=15;

LL l,r,f[MXX][MXX],a[MXX];

LL DFS(LL pos,LL num,LL st,bool lead,bool limit)
{
if(!pos) Heriko st;
if(!limit and lead and f[pos][st]!=-1) Heriko f[pos][st];
LL n(limit?a[pos]:9),res(0);
for(R LL i(0);i<=n;++i) res+=DFS(pos-1,num,st+((i or lead) and (i==num)),(lead or i),((i==n) and limit));
if(!limit and lead) f[pos][st]=res;
Heriko res;
}

I LL DP(LL x,LL y)
{
mst(f,-1);LL len(0);
while(x)
    {
a[++len]=x%10;
x/=10;
    }
Heriko DFS(len,y,0,0,1);
}

S main()
{
fr(l),fr(r);
for(R LL i(0);i<=9;++i) fw(DP(r,i)-DP(l-1,i),0);
Heriko Deltana;
}
数位 #define 数组 搜索 #include
上一篇: 摆花 （DP动态规划）
下一篇: 动态规划之插头DP入门

继续阅读