嘛是数位DP？
数位 DP 一般都较模板化(目前来说也就会一点简单的),
往往需要改变的是 DFS 里面的参数和递归的条件(你说
来简单,一下手就凉凉)。
常见问法:
在区间 [l,r] 内 符合某种条件的数有多少个,或者有多少种方案？
基本变量:
pos : 位数,因人而异(我是从高位开始枚举)
st : 答案
limit : 最高位限制
(拿 12345 这个数来说,第一位取 0 的话 第二位可以 取 0 ~ 9
但是第一位 取 1 的话, 第二位就只能取 0 ~ 2,依次类推)
其他变量:
pre : 记录前一位
lead : 判断是否有前导 0 （Windy 数）
板子:
/*
1、求一个区间时往往分解成两个区间 [1,l-1],[1,r];
然后最后相减即可(因为这样我们可以只考虑上限,相对来说
更加简单)
2、初始化:
a、 memset(dp,-1,sizeof(dp));
(某些时候数量会为 0)
b、分解 l 或者 r
3、DFS(pos,st,limit) -- 基本变量
/*
// 大佬的板子
ll dfs(int pos,int pre,int st,……,int lead,int limit)//记搜
{
if(pos == -1) return st;//剪枝
if((dp[pos][pre][st]……[……]!=-1&&(!limit)&&(!lead))) return dp[pos][pre][st]……[……];//记录当前值
ll ret=0;//暂时记录当前方案数
int res=limit?a[len-pos+1]:9;//res当前位能取到的最大值
for(int i=0;i<=res;i++)
{
//有前导0并且当前位也是前导0
if((!i)&&lead) ret+=dfs(……,……,……,i==res&&limit);
//有前导0但当前位不是前导0，当前位就是最高位
else if(i&&lead) ret+=dfs(……,……,……,i==res&&limit);
else if(根据题意而定的判断) ret+=dfs(……,……,……,i==res&&limit);
}
if(!limit&&!lead) dp[pos][pre][st]……[……]=ret;//当前状态方案数记录
return ret;
}
ll part(ll x)//把数按位拆分
{
len=0;
while(x) a[++len]=x%10,x/=10;
memset(dp,-1,sizeof dp);//初始化-1（因为有可能某些情况下的方案数是0）
return dfs(……,……,……,……);//进入记搜
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld",&l,&r);
if(l) printf("%lld",part(r)-part(l-1));//[l,r](l!=0)
else printf("%lld",part(r)-part(l));//从0开始要特判
}
return 0;
}
例题:
题目链接:
不要62
Code:
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 15;
int dp[maxn][maxn],a[maxn];
int l,r;
int DFS(int pos,int st,bool limit) {
// 说明都扩展完了
if(pos == -1) return 1;
// 优化,记忆化搜索,如果不是最高位并且已经有值了,直接返回即可
if(!limit && dp[pos][st] != -1) return dp[pos][st];
int ans = 0;
// 判断前一个是否是最高位(某大佬说的贴着放)
int up = limit ? a[pos] : 9;
for(int i = 0; i <= up; i ++) {
// 统计没有 4 和 62 的数
if(i == 4 || (st == 6 && i == 2)) continue;
else {
// 第三个参数: 前一位是最高位,并且当前位也是最高位
ans += DFS(pos - 1,i,limit && i == a[pos]);
}
}
// 优化,如果不是最高位,就记录一下,便于下一次直接用
if(!limit) dp[pos][st] = ans;
return ans;
}
int solve(int x) {
int len = 0;
while(x) {
a[len ++] = x % 10;
x /= 10;
}
// 刚开始的时候肯定是最高位
return DFS(len - 1,0,1);
}
int main(void) {
while(scanf("%d%d",&l,&r) != EOF) {
if(l == 0 && r == 0) break;
memset(dp,-1,sizeof(dp));
int R = solve(r);
int L = solve(l - 1);
printf("%d
",R - L);
}
return 0;
}
其他例题:
Bomb
不要62
Windy数
数字计数
大佬博客:
https://www.luogu.com.cn/blog/virus2017/shuweidp