【递推型】数位 DP

· · 算法·理论

本文章同步发表在博客园。

什么是数位 DP？

数位 DP 通常用来统计区间 [L,R] 内满足某限制的数字数量。通常 L 和 R 的数据范围较大，只能用 DP 来统计。

上界 R 的处理技巧

由数值的比较规则可知，当前数位的取值范围与靠前数位的值有关。

如果靠前的所有数位都与 R 相同，则当前数位的值不能大于 R 中当前位的数值。相反，如果靠前的数位中存在比 R 小的数位，则当前数位的值没有限制，可以取 0 \sim 9 中的任意一个数。

整体来说就是任意时候当前数均不能大于 R 的对应前缀。

因此，状态中需要一个关于上界的标记 ub，表示靠前位与 R 是否存在过不同。

转移时，如果靠前位或者当前位与 R 不同，则转移后标记为 1，反之为 0。

如果单独考虑 ub=0 的情况

由于当位数为 k 时，ub = 0 的情况只有一种，那我们就可以考虑把这一种情况单独拎出来讨论，并单独转移。

这样能使代码变得更清晰……吗？

其实上非也。

如果同时有多个数据限制 [L_i,R_i]，这种方法就会上容斥，实现难度指数级增长。

因此不建议使用该方法。

下界 L 的处理技巧

下界 L 的处理技巧？没搞错吧，一般都是用容斥的啊，不存在下界 L 啊！

啊对对对，你说的很对，但是你先别急，你听我说。

如果不用容斥法儿，那就要考虑下界 L 的处理情况。简单，加一个 lb 的下界标记，跟上界标记同样的操作。

那么现在问题就来了，到底是加下界的方案好呢，还是常规的容斥法好呢？

答案是前者。

为什么？这么轻易下定论，难道连个理由都没有？要知道后者是最常用的啊喂！

是的是的，但是你自认为后者少去了下界标记 lb，但实质上不然。

因为后者还需要考虑前导零。考虑前导零，实质上就等同于在考虑一个下界标记，只不过 L = 0 罢了。

而且，同样的，如果有多个范围限制，这东西又得上容斥，特麻烦。

故推荐前者写法。（当然并不是阻止你用容斥写法！你想用还是可以用滴！）

经典例题分析

这里选用 P2657 windy 数 作为例题进行讲解。

读入时统一用字符串读入并补充 L 中所需要的前导零。

考虑如何定义 dp 数组的状态。

不难想到状态中应存在：

综上所述我们可以定义出一个四维的 dp 数组。

接下来考虑转移。

首先我们枚举 i（当前枚举位数）、x（下界标记）、y（上界标记）以及上一位的数字 j。为什么要枚举它？因为它要用来辅助转移。

接下来枚举当前位数字 k。这个数字 k 的取值范围就和 x 以及 y 挂钩了。如果 x=1，那么 k 的下界不受限，否则受 L 的限制；同样的，如果 y=1，那么 k 的上界不受限，否则受 R 的限制。

那么接下来就可以转移了。我的转移是扩散型的。

可以秒算出新一轮的 x 和 y（记为 u 和 v）。转移式很简单，就是 dp_{i+1,u,v,k} = dp_{i+1,u,v,k} + dp_{i,x,y,j}，但是转移需要满足条件：|j-k| \ge 2。因为这是题目的限制嘛！

不过这个条件少了一点。如果现在还处在前导零范围，那我们就不需要保证这个条件了，所以需要再特判一下 x=0 并且 i 还处在前导零范围内的情况。

那么这个题目就结束了。

代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
string a,b;LL ch,n,dp[20][2][2][10],ans;
int main(){
    cin>>a>>b;n=b.size(),ch=n-a.size();
    while(a.size()<n)a="0"+a;dp[0][0][0][0]=1;
    for(int i=0;i<n;i++)for(int x=0;x<2;x++)
        for(int y=0;y<2;y++)for(int j=0;j<=9;j++)
            for(int k=(x?0:a[i]-'0');k<=(y?9:b[i]-'0');k++){
                int u=(x||k>(a[i]-'0')),v=(y||k<(b[i]-'0'));
                if((!x&&i<=ch)||abs(j-k)>1)dp[i+1][u][v][k]+=dp[i][x][y][j];
            }
    for(int x=0;x<2;x++)for(int y=0;y<2;y++)
        for(int j=0;j<=9;j++)ans+=dp[n][x][y][j];
    cout<<ans<<"\n";
    return 0;
}

P.S.这份代码同样也可以通过 加强版 的数据。双倍经验！这可是一黄一蓝啊！

第二道例题详解

这道例题为 P6218 Round Numbers S。

这个例题算是比较简单的了。

首先由于 DP 处理的时候是用二进制处理的，所以一开始先把 l 和 r 都转化为二进制（用字符串存储）。

接下来考虑 DP 的状态设计。

由于二进制顶多 31 位随便搞都能过，所以不妨大胆一点，设 dp_{i,p,q,x,y} 表示当前考虑了前 i 位，这之中有 p 个有效的 0，并有 q 个 1，下界标记为 x，上界标记为 y 时的「圆数」数量。

什么样的 0 才被称为有效的？显然，前导零绝对是无效的，要不然还 DP 干嘛？只要加足够多的前导零，所有数都能称为「圆数」！

因此这是本题一个坑点之一，你需要特殊判断一下前导零不能算进 p 里。

其他的话，转移和上一题比较相似，也要枚举 k，但是这一次不需要枚举 j 了。因为 j 对转移不起任何作用。

最后累加答案的时候枚举 x 和 y，以及 p 和 q。当然了只有 p \ge q 的答案才能统计进去。

代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL l,r,n,ch,dp[40][40][40][2][2],ans;string L,R;
int main(){
    cin>>l>>r;dp[0][0][0][0][0]=1;
    while(l)L=(char)(l%2+'0')+L,l>>=1;
    while(r)R=(char)(r%2+'0')+R,r>>=1;
    n=R.size();ch=n-L.size();while(L.size()<n)L="0"+L;
    for(int i=0;i<n;i++)for(int x=0;x<2;x++)
        for(int y=0;y<2;y++)for(int p=0;p<=i;p++)for(int q=0;p+q<=i;q++)
            for(int k=(x?0:L[i]-'0');k<=(y?1:R[i]-'0');k++){
                int nx=(x||k>(L[i]-'0')),ny=(y||k<(R[i]-'0'));
                dp[i+1][p+(!k&&(!(!x&&i<=ch)))][q+(k)][nx][ny]+=dp[i][p][q][x][y];
            }
    for(int p=0;p<=n;p++)for(int q=0;p+q<=n&&q<=p;q++)
        for(int x=0;x<2;x++)for(int y=0;y<2;y++)ans+=dp[n][p][q][x][y];
    cout<<ans<<"\n";
    return 0;
}

初试身手——例 3

这道例题为 同类分布。

注意到各位数字之和随着 DP 的推进在不断变换。这样很难处理，不能存取模后的值，但原值过大根本无法记录。

怎么办？凉拌炒鸡蛋，好吃又好看！

其实上很简单。反正数据范围不算很大，那就暴力一点嘛！在外面套一个大的循环，枚举最终的各位数字之和。这样就可以记录了。

重述一遍，定义 dp_{i,f,p,x} 表示当前考虑了前 i 位，目前的各位数字之和为 f，目前总值取模后结果为 p，上下界情况压缩为二进制存储进 x 中。

主要转移难度在于创造新的 x、f 和 p。x 是常规操作，就不多叙述了，f 很简单，加上当前数 k 就行，而 p 需要先 \times 10 然后加上 k，再取模，才行。

整个来说也不算很难吧。

代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
string L,R;
LL n,ch,dp[20][200][200][5],ans;
void init(int N){
  for(int i=0;i<=n;i++)for(int j=0;j<=N;j++)
    for(int k=0;k<=N;k++)for(int x=0;x<4;x++)dp[i][j][k][x]=0;
  dp[0][0][0][0]=1;return;
}
int main(){
  cin>>L>>R;n=R.size(),ch=n-L.size();
  while(L.size()<n)L="0"+L;
  for(int mod=1;mod<=n*9;mod++){
    init(mod);
    for(int i=0;i<n;i++)for(int f=0;f<=mod;f++)
      for(int o=0;o<4;o++)for(int p=0;p<=mod;p++)
          for(int k=(o&1?0:L[i]-'0');k<=(o&2?9:R[i]-'0')&&f+k<=mod;k++){
            if(!dp[i][f][p][o])continue;
            int u=(o&1||k>(L[i]-'0')),v=(o&2||k<(R[i]-'0'));
            dp[i+1][f+k][(p*10+k)%mod][u|(v*2)]+=dp[i][f][p][o];
          }
    for(int x=0;x<4;x++)ans+=dp[n][mod][0][x];
  }
  cout<<ans<<"\n";
  return 0;
}

简单总结概括一下

学数位 DP 之前，我一直以为大多题目都是绿的。现在我才知道，数位 DP 的题都是蓝起步吗？我都看到一堆紫题了。

数位 DP，大多人都喜欢写记忆化搜索。一翻题解区，记搜占满大几页，想找个递推的题解都难。大家似乎都认为记搜更优，而我不这么认为。我认为正常的递推比较清晰方便，也比较好写。

可以发现，其实上数位 DP 的套路基本都是一样的，一个板子套在所有题上。只需要稍微修一修中间的一些细节，多加几层循环之类的，就能够又过一个题。

而在这之中，上下界标记是精华。

顺便提一嘴，由于数位 DP 通常定的维数都比较多，所以它常和状压挂钩。你经常需要把各种东西压成一个二进制数来表示，这样能使你的代码简略不少，还能减少你的常数。

码这么多字也不容易，还希望各位留个赞支持一下，真是太感谢啦！