动态规划-数位dp

Posted on | In , | Visitors:

This is my blog.

做CCPC的时候，被一道题卡着了，然后看了题解还是不会的我

是不是要完蛋了呀！

然后就开始写数位dp的题目了

为了表达一下这篇文章的博主的敬佩之情，特此献上链接，你看过他的就不用看我的了……

一直以为dp最后都可以化成几个for循环，然后用等式写出来的形式，但是很不凑巧的是，数位dp基本不是这样的

最近看了Candy？的博客，发现，嗯，也可以写，同时也很好懂！！！

但是当题目特别麻烦的时候，还是用dfs吧！

过了几天，看他最近写的题目发现都改用dfs了，那就dfs好啦！

写了两天的数位dp，改bug到疯掉，打算先歇息一会，写点别的题目了，之后再来写啦！

for循环的方法

这个方法的主要操作，就是先预处理没有界限的所有数据

在每次询问的时候，对于多处的部分再进行分类讨论

我们还是拿讲数位dp最经典的题目hdu 2089来说

首先也是以第一位当作第pos位，第二位当作状态

1
2
3
4
5
dp[i][0]第i位没有不吉利
dp[i][1]没有不吉利且第i位是2
dp[i][2]有不吉利

基本板子

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=10;
int l,r;
int d[N][4];
int digit[N];
void dp(){
    d[0][0]=1;
    for(int i=1;i<=6;i++){
        //这里情况的处理
        d[i][0]=9*d[i-1][0]-d[i-1][1];
        d[i][1]=d[i-1][0];
        d[i][2]=10*d[i-1][2]+d[i-1][1]+d[i-1][0];
    }
}
int sol(int n){
    int cnt=0;
    while(n){
        digit[++cnt]=n%10;
        n/=10;
    }
    digit[cnt+1]=0;
    int flag=0;int _n=n,ans=0;
    for(int i=cnt;i>=1;i--){
        //以及这里的处理
        ans+=d[i-1][2]*digit[i];
        
        if(flag) ans+=digit[i]*d[i-1][0];
        else{
            if(digit[i]>4) ans+=d[i-1][0];//maybe 4
            if(digit[i+1]==6&&digit[i]>2) ans+=d[i][1];//maybe 62
            if(digit[i]>6) ans+=d[i-1][1];//maybe 62 对于上面两条来说，一个判断过之后，会有flag=1来制约的
        }
        if(digit[i]==4||(digit[i+1]==6&&digit[i]==2)) flag=1;
    }
    return _n-ans;
}
int main() {
    dp();
    while(scanf("%d%d",&l,&r)&&l+r)
        printf("%d\n",sol(r+1)-sol(l));
    return 0;
}

经典题目

因为刚开始没有练这种方法，所以只有之后的题目，将两种方法都写了

Hdu 2089

找出区间内不可以是连续62或4的个数，这里也默认总共n位对结果没有影响

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//dp[i][0]第i位没有不吉利
//dp[i][1]没有不吉利且第i位是2
//dp[i][2]有不吉利
//no limit
d[i][0]=9*d[i-1][0]-d[i-1][1];
d[i][1]=d[i-1][0];
d[i][2]=10*d[i-1][2]+d[i-1][1]+d[i-1][0];
//have limit
	for(int i=cnt;i>=1;i--){
        ans+=d[i-1][2]*digit[i];
        
        if(flag) ans+=digit[i]*d[i-1][0];
        else{
            if(digit[i]>4) ans+=d[i-1][0];
            if(digit[i+1]==6&&digit[i]>2) ans+=d[i][1];
            if(digit[i]>6) ans+=d[i-1][1];
        }
        if(digit[i]==4||(digit[i+1]==6&&digit[i]==2)) flag=1;
    }

Hdu 3555

找到范围内有连续“49”出现的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//dp[i][0]到第i位没有49且这位也没有隐患
//dp[i][1]没有不吉利且第i位是9
//dp[i][2]有49
//no limit
d[i][0]=10*d[i-1][0]-d[i-1][1];
d[i][1]=d[i-1][0];
d[i][2]=10*d[i-1][2]+d[i-1][1];
//have limit
	for(int i=cnt;i>=1;i--){
        ans+=d[i-1][2]*digit[i];
        
        if(flag) ans+=digit[i]*d[i-1][0];
        else if(digit[i]>4) ans+=d[i-1][1];//maybe 49
        if(digit[i+1]==4&&digit[i]==9) flag=1;
    }

dfs的方法

基本思想

数位dp基本的思想就是通过枚举每一位的数字，计算这个数字下的状态值是多少；

数位dp的优化就是记忆话搜索，在没有这一位的取值位i的时候，低位的取值没有限制的时候，记录下这时候 的dp[pos][status]的值，这样在多组查询的时候，若遇到仍在此位此状态下且对低位没有要求的时候，这个值应该是相等的，也就是说如果pos==2的时候，dp[pos][status]记录的是200-299状态下所有符合要求的答案的值；

所需考虑因素

在数位dp中，一个限制是，可能在计算的时候不是计算完整的（比如给的范围是232，而不是299);

第二个限制是由于前导零产生，会导致0，00重复被计算；也是因为这个原因导致我的数位dp一直用的是dfs+记忆化搜索（不过其实前导零有影响的题目，目前遇到的比较少

所以现在对于每一道题目，我所需要思考的是：

  • 这个前导零会不会影响结果，比如hdu2089（计算区间内没有4和连续62的个数，因为这是一个车牌，所以可以允许前导零的出现）；又比如hdu4734，因为在我们计算的时候，可以默认每一个数字都是n位，因为（前面的0对于整个公式来说不会影响值；可以看一下经典题目里面，感觉我语言表达不了
  • 状态的设计是什么，不可以超出数组的范围
  • 结果是不是只是统计个数，还是有什么运算，若是运算是否可以化简

暂时还没有想到其他的问题；这样看来似乎状态设计就可以简单一点；

运用环境

那么下一个问题就是什么时候我们需要用到数位dp呢？

  • 首当其冲的就是计算某个区间内，某个数字出现或不出现的个数
  • 计算某个区间内，每一个数字出现的个数
  • 计算某个区间内，满足某个数字比另一个数字多的个数
  • 当然也可以是，通过一个算式对每一位进行运算后，结果满足什么条件的时候
  • 也可以是，这个数字的每一位满足只升不降，只降不升，先升后降，先降后升顺序的个数

也就是说要和数字每一位有关的时候

优势

那么它为什么好用呢？

因为通常数字很大的时候，我们如果按照位来做的话，这个数量级就不是一个级别的了！

这也是很多时候有些大数的题目转换成字符串来做的原因呢！

基本板子

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=105;
const int maxx=120;//状态数
const int mod=1e9+7;
ll dp[maxn][maxx];
int digit[maxn];
int n,m;
//status满足什么条件的数位dp
ll dfs(int pos,int status,bool limit,bool lead){//lead表示没有前导零，limit表示是否有限制
    if(pos==0&&status>=x) return 1;//这里需要进行修改
    if(!limit&&!lead&&dp[pos][status]!=-1) return dp[pos][status];
    int up=limit?digit[pos]:9;//二进制下是1
    ll tmp=0;
    for(int i=0;i<=up;i++){
        if(lead&&i==0) tmp+=dfs(pos-1,status,limit&&i==digit[pos],lead);
        else tmp+=dfs(pos-1,status+y,limit&&digit[pos]==i,lead&&i==0);
    }
    if(!limit&&!lead) dp[pos][status]=tmp;
    return tmp;
}
ll solve(int n){
    int cnt=0;
    while(n){
        digit[++cnt]=n%10;
        n/=10;
    }
    return dfs(cnt,0,true,true);
}
int main(){
    memset(dp,-1,sizeof(dp));
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d",n,&m);
        printf("%lld\n",solve(n)-solve(m-1));//注意给的区间如果是闭区间的话，这里需要solve(m-1)
    }
}

经典题目

Hdu 6148

找出到n为止，满足每一个数位的数字不是先升后降的个数；因为要和前面的数字比较，如果有前导零的时候，这个数字不可以和零比较直接得出是升序，而应该是一个不确定序列

1
2
3
4
5
6
7
//设置dp数组为3维			ll dp[pos][pre][turn];
ll dfs(int pos,int pre,int turn,bool limit,bool lead){
    //turn表示0 暂不确定（比如只有一个数字，或者前面的数字全是相等的时候，1表示上升，2表示下降
    //pre表示上一位的数字是什么，这样可以确定这一位的turn
    //在刚开始进入的时候，pre设置为零，这样可以表示012的升，也可以表示098的降
    //同时turn设置为0
}

Hdu 4734

找出0，B范围所有运用公式f(x)的值小于等于f(A)的个数

1
2
3
4
5
//int dp[pos][sum]
int dfs(int pos,bool limit,int sum){
    //需满足剩下位数运用公式计算后的值的和不可以超过sum
    //初始状态下sum=f(A)
}

Hdu 3252

找出start到finish范围内所有满足在二进制表示下0的个数超过1的个数的数字的个数

1
2
3
4
5
6
7
//ll dp[pos][status];
ll dfs(int pos,int status,bool limit,bool lead){
    //status表示0的个数减去1的个数的值
    //只有当最后一位处理完后，status仍大于等于0的时候才满足条件
    //因为可以是全1，这样status会有负数出现，不便于记忆化
    //所以我们以32为新零点，这样最后判断是否均大于32即可
}

Hdu 2089

找出区间内不可以是连续62或4的个数，这里也默认总共n位对结果没有影响

1
2
3
4
//ll dp[pos][state];
ll dfs(int pos,bool limit,bool state){
    //state代表这一位是否是6
}

Hdu 4507

题目要求找出指定区间内满足：

1、整数中某一位是7；

2、整数的每一位加起来的和是7的整数倍；

3、这个整数是7的整数倍；

的数的平方和

1
2
3
4
5
6
//status dp[pos][remainder_sum][remainder];
status dfs(int pos,bool limit,int remainder_sum,int remainder){
    //remainder_sum 每一位数字和除以7的余数 
    //remainder 这个整数的和除以7的余数
    //所以易知下一个dfs(pos-1,limit&&i==digit[pos],(remainder_sum+i)%7,(remainder*10+i)%7)
}

虽然设计对状态的我，但是还有好多细节：

  • 首先，题目求的是数的平方之和，因此我们不可以简单相加

    • 这个新的数字是$i*10^{pos}+x$，要加上这个数字的平方；

    • 这里的x应该是dfs下一个组成的数值，而这个数字有很多

    • 同时我们所求的是平方和，而我们通过平方和是得不到这个x的，因为里面已经有$a^2+b^2+\cdot\cdot\cdot+x+\cdot\cdot\cdot+n^2$了，于是我们需要用结构体存a,b,……,n的值，即就是现在组成所有合法的数字

    • 以及目前这些数字的平方和，作为之后的答案；

    • 但这样子，首先占用的内存很大，其次对于这些我们可以进行化简

      • 新数字之和sum=$i10^{pos}cnt+(a+b+\cdot\cdot\cdot+n)=i10^{pos}cnt+上一个新数字之和sum$

      • 而cnt其实和普通的数位dp一样，是cnt+=next.cnt

      • 我们所求的答案$sum2=sum2+\sum(i*10^{pos}+x)^2$

        展开得$sum2=sum2+next.cnti^210^{2pos}+2i10^{pos}next.sum+next.sum2$

      • 因此我们可以只存3个数字即cnt，sum，sum2

    • 其余按正常dp走就可以

  • 再者这道题数字很大，很容易溢出（毕竟平方么，所以需要多mod，同时对于ten也要开longlong什么的，防止中间运算的时候溢出，预处理那里也可能用int会溢出啦

  • 且由于取mod之后，solve(r)的值也可能会比solve(l-1)的值要小，所以需要加mod再取模

Bzoj 1026

找到范围内所有满足相邻位的值相差大于等于2的个数

1
2
3
//ll dp[pos][pre]
ll dfs(int pos,bool limit,bool lead,int pre){
}
  • 注意只有在!limit&&!lead的时候，才可以更新答案
  • 同时pos==0&&!lead的时候才可以返回1，否则返回0；因为所有位赋完值后，还有前导零的话，就代表没有变成一个数

Hdu 3555

找到范围内有连续“49”出现的个数

1
2
3
4
//ll dp[pos]
ll dfs(int pos,bool four,bool limit){
    //four上一位是不是4
}

两种方法的比较

其实两种的方法的思维方式是一样的，甚至代码长度都差不多；

但是第一种看起来更厉害一些，所以，看大家的习惯啦

代刷的题目

hdu 4352

Hdu 3709

Hdu 3652

luogu P3414

POJ 3689

bzoj 1799

bzoj 3530

bzoj 1833

bzoj 3329

bzoj 3209

bzoj 4513

Cf 388D

后记

2018.08.29

嚯嚯嚯！新耳机到啦！

想到未来美美的样子，就信心十足

做个得意的表情吧！

转载请注明出处，谢谢。

愿 我是你的小太阳

买糖果去喽