数位DP不写DFS难道是正解?
再次修改,为了复习
题目描述
枚举不含前导零且相邻两个数字之差至少为 2 的正整数
推荐的数位DP讲解 洛谷日报
Analysis
可以看到A与B的范围很大,但是想一想他们的数位并不会超过9,这不就正好符合数位DP的套路吗?
首先明确这个状态怎么设计:
每一位的取值都与前一位有关,也解释说当我们枚到第pos层时,这一层一第pos+1层有关,那么我们
就设f[pos][las]为在第pos层以las开头的符合要求的数的数量
诠释过程:
枚举总会有一个限制,这便是边界,我们需要对边界的每一位进行分解,同时用一个变量标记是否有
最高位限制
int ed=(limit) ? k[dep]:9;
其实很好理解。
打个比方,你能吃5432个鸡腿,已经吃了5000个了,还能吃多少个呢?432。即,在百位上最多是4。
然后根据这个范围,再加上题目要求的判断
ret+=dfs(lead&&(!i),limit&&(i==ed),dep-1,i);
代码时间
`
//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")
//手动优化
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define RG register
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=35,M=11;
int f[N][M],k[N];//每一位的限制
int a,b;//范围
inline int dfs(bool lead,bool limit,int dep,int las)
{
if(!dep) return 1;
if(!lead&&!limit&&(~f[dep][las])) return f[dep][las];
int ret=0;
int ed=(limit) ? k[dep]:9;
// printf("1___ ed= %d\n",ed);
for (int i=0;i<=ed;i++)
if(lead||abs(i-las)>=2)
//只要当前选的数和上一次相差2就行了
{
ret+=dfs(lead&&(!i),limit&&(i==ed),dep-1,i);
// printf("2___ ret= %d\n",ret);
}
if(!lead&&!limit) f[dep][las]=ret;
return ret;
}
inline int dp(int n)
{
int cnt=0;
if(!n) return 1;
while(n) k[++cnt]=n%10,n/=10;//对每一位进行分解
int res=0;
for (int i=0;i<=k[cnt];i++)
res+=dfs((!i),i==k[cnt],cnt-1,i);
return res;
}
int main()
{
memset(f,-1,sizeof(f));//初始
scanf("%d%d",&a,&b);
printf("%d\n",dp(b)-dp(a-1));
//差分思想
return 0;
}
`
感谢大佬的分享!!!