数位dp

数位dp

简介

数位dp是一种一般用来计数的dp，常用于求解\(l-r\)之间有多少符合条件的数的问题，由于\(l,r\)一般给的很大，所以无法用直接遍历的方法求解，这时候就要用到数位dp了。

模板

long long digit[maxn];
long long dp[30][state];//二位dp数，第一维是数位，第二维是状态数

long long dfs(int pos/*数位*/, int state/*状态记录*/, bool limit/*数位上界辅助确定数组*/, bool lead/*确定数组前导0*/)
{
	if(pos == -1) return 1;//数位遍历结束，返回求解
	if(!limit && !lead && dp[pos][state] != -1) return dp[pos][state];
	//记忆化，直接返回值
	int upbd = limit ? digit[pos] : 9;//确定数组上界

	for(int i = 0; i <= upbd; i++)
	{
		if(bool state_1) continue;
		else if(bool state_2) continue;
		.
		.
		.
		//排除所有不满足要求的数
		ans += dfs(pos - 1, state, limit && i == upbd, lead && i == 0);//根据实际情况变更变量值
	}
	if(!limit && !lead) dp[pos][state] = ans;
	//记忆化，记录结果
	return ans;
}

long long get_num(int x)
{
	int pos = 0;
	while(x)
	{
		digit[pos++] = x % 10;
		x /= 10;
	}//初始化数位数组
	return dfs(pos - 1, state, true, true);//返回对应结果，从高位向低位求解
}

解析

dfs结合dp数组记录搜索结果，也就是实现记忆化，在dfs时记录了前导零标记和最高位标记，这里比较好理解，对于最高位，前导零肯定是允许存在的，对于中间位前导零是不允许的，而对于每位的上界又limit辅助确定，如果前一位等于\(digit[pos]\)也是就是恰好等于允许出现的最高位，那么下一位上界也只能是\(digit[pos]\)，如果前一位小于允许的上界，那么下一位就有\(0——9\)所有可能。这样不断深搜结合记忆化，便可以快速得到正确答案，在这里看来，数位dp或许是一种更加优美的暴力算法。

例题

题目描述

杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：62315,73418,88914都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今后又要实际上给多少辆新的士车上牌照了。

输入

输入的都是整数对n,m，如果遇到都是0的整数对，则输入结束。

输出

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

样例输入

1 100

0 0

样例输出

80

Hint

\(0 < n \leq m < 10^7\)

思路：模板题，注意记录6的状态

#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define CSE(x,y) memset(x,y,sizeof(x))
#define INF 0x3f3f3f3f
#define Abs(x) (x>=0?x:(-x))
#define FAST ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll , ll> pll;
 
const int maxn=111111;
ll dp[30][20];
int a[30];
 
ll dfs(int pos, int state,bool lead, bool limit)
{
    if(pos == -1) return 1;
    if(!limit && !lead && dp[pos][state] != -1) return dp[pos][state];
    int up = limit ? a[pos] : 9;
    ll ans = 0;
    for(int i = 0; i <= up; i++)
    {
        if(i == 4) continue;
        else if(state == 6 && i == 2) continue;
        ans += dfs(pos - 1, i, lead && i == 0, limit && i == a[pos]);
    }
    if(!limit && !lead)
        dp[pos][state] = ans;
    return ans;
}
 
ll get_num(ll x)
{
    int pos = 0;
    while(x)
    {
        a[pos++] = x % 10;
        x /= 10;
    }
    return dfs(pos - 1, 0, true, true);
}
 
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    #endif
    FAST;
    int l , r;
    while(cin >> l >> r && l && r){
        CSE(dp, -1);
        cout << get_num(r) - get_num(l - 1) << endl;
    }   
    return 0;
}