SkyWT / 博客 / 数位 DP 入门:HDU 3555 Bomb

数位 DP 入门:HDU 3555 Bomb

2018 年 9 月 27 日 05:40


文章目录

简单来说,数位 DP 大概就是把一个数字拆开按位进行 DP 的一种思想。

HDU 3555 Bomb

The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence "49", the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?

Hint

数位 DP 的典型入门题,解法很多。

Analysis #1

这题“包含 49 的数字数量”比较难构造,所以我们决定构造“不包含 49 的数字数量”。

DP 构造

F[i][j]:最高位为 j 的 i 位数字中不包含 49 的数字数量。

F(i,j)=k[0,9]k9j4F(i1,k)F(i,j) = \sum_{k\in [0,9]}^{k \not = 9 \text{或} j \not = 4} F(i-1,k)

inline void make_dp(){
    for (int i=0;i<=9;i++) f[1][i]=1;
    for (int i=2;i<=22;i++)
    for (int j=0;j<=9;j++)
    for (int k=0;k<=9;k++){
        if (j==4&&k==9) continue;
        f[i][j]+=f[i-1][k];
    }
}

答案累计

首先将数字按位分离,然后按位统计。

对于从高到低第 ii 位数字 AiA_i,首先肯定要累计上 j=0j<AiF(i,j)\sum_{j=0}^{j < A_i} F(i,j),也就是这一位小于 AiA_i 的数字数量。至于这一位等于 AiA_i 的情况,就是之后处理的了。所以需要判断一下:如果出现了 49 这个数字就退出。

inline int calculate(int x){
    int ret=0;
    spread_number(x);
    for (int i=a[0];i>=1;i--){
        for (int j=0;j<a[i];j++) ret+=f[i][j];
        if (a[i]==9&&a[i+1]==4) break;
    }
    return ret;
}

代码

/*
 * Vjudge CONTEST257056 数位DP专题练习
 * B - Bomb
 * 180927 By SkyWT
 */

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>

using namespace std;

#define memset_clear(_) memset(_,0,sizeof(_))
#define memset_clear_tre(_) memset(_,1,sizeof(_))
#define memset_clear_reg(_) memset(_,-1,sizeof(_))
#define memset_clear_max(_) memset(_,0x3f,sizeof(_))
#define memset_clear_min(_) memset(_,0x80,sizeof(_))
#define sqr(_) ((_)*(_))

#define write(_) cout<<#_<<" = "<<_<<endl
#define write_2(_,__) cout<<#_<<" = "<<_<<" , "<<#__<<" = "<<__<<endl
#define write_3(_,__,___) cout<<#_<<" = "<<_<<" , "<<#__<<" = "<<__<<" , "<<#___<<" = "<<___<<endl

#define int long long

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

int T,n;
int f[25][11],a[25];

inline void make_dp(){
    for (int i=0;i<=9;i++) f[1][i]=1;
    for (int i=2;i<=22;i++)
    for (int j=0;j<=9;j++)
    for (int k=0;k<=9;k++){
        if (j==4&&k==9) continue;
        f[i][j]+=f[i-1][k];
    }
}

inline void spread_number(int x){
    memset_clear(a);
    while (x) a[++a[0]]=x%10,x/=10;
}

inline int calculate(int x){
    int ret=0;
    spread_number(x);
    for (int i=a[0];i>=1;i--){
        for (int j=0;j<a[i];j++) ret+=f[i][j];
        if (a[i]==9&&a[i+1]==4) break;
    }
    return ret;
}

signed main(){
    make_dp();
    T=read();
    while (T--){
        n=read();
        printf("%lld\n",n+1-calculate(n+1));
    }
    return 0;
}

Analysis #2

这种方法相较上一种,空间和时间上只达到了常数的优化。不过还是值得研究下~

DP 构造

这个 DP 的定义比刚才的要简单一点:

  • F[i][0]:数字长度为 i,首位为任意数字,不包含 49 的数字数量
  • F[i][1]:数字长度为 i,首位为 9,不包含 49 的数字数量
  • F[i][2]:数字长度为 i,包含 49 的数量

转移方程如下:

F(i,0)=F(i1,0)10F(i1,1)F(i,0)=F(i-1,0)\ast 10-F(i-1,1)

(很好理解,要减去出现了 49 的情况)

F(i,1)=F(i1,0)F(i,1)=F(i-1,0)

F(i,2)=F(i1,2)10+F(i1,1)F(i,2)=F(i-1,2)\ast 10+F(i-1,1)

(要加上这位为 4、后一位为 9 的情况)

答案累计

答案的累计和上面解法差不多。

Analysis #3

这题其实还可以用记忆化搜索。数位 DP 用记忆化搜索解决会很方便~

代码

以下是 HEXU 大佬的代码……

#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
const int N = 100 + 5;

ll f[N][N];
int digit[N];

ll dfs(int pos, int flag, int limit) {
    if (pos <= 0) return 1;
    if (! limit && f[pos][flag] != -1) return f[pos][flag];
    int up = limit ? digit[pos] : 9; ll cur = 0;
    
    for (int i = 0; i <= up; ++ i) {
        if (flag == 1 && i == 9) continue;
        cur += dfs(pos - 1, i == 4, limit && i == up);
    }
    return limit ? cur : f[pos][flag] = cur;
}

ll Solve(ll x) {
    memset(digit, 0, sizeof(digit)); int len = 0;
    for (; x; x /= 10) digit[++ len] = x % 10;
    return dfs(len, 0, 1);
}

int main(void) {
    memset(f, -1, sizeof(f));
    int T; scanf("%d", &T);
    while (T --) {
        ll r; scanf("%lld", &r);
        printf("%lld\n", r + 1 - Solve(r));
    }
    return 0;
}

暂无评论


发表新的评论

所有评论都将经过博主审核。请勿填写无意义邮箱或发表无关评论、广告等,否则会被视为垃圾评论。

提交评论即表明你同意本网站使用 Cookie,并允许本站在后台记录你的邮箱、IP 地址等必要信息。这些信息不会被透露给其他用户。(提交一次评论后,本提示将不再展示)