简单来说,数位 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) = \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];
}
}
答案累计
首先将数字按位分离,然后按位统计。
对于从高到低第 $i$ 位数字 $A_i$,首先肯定要累计上 $\sum_{j=0}^{j < A_i} F(i,j)$,也就是这一位小于 $A_i$ 的数字数量。至于这一位等于 $A_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(i-1,0)\ast 10-F(i-1,1)$$
(很好理解,要减去出现了 49 的情况)
$$F(i,1)=F(i-1,0)$$
$$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;
}