【洛谷P2657】[SCOI2009] windy数

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

最近学习了一下数位DP

感觉记忆化搜索是比较好理解的

这篇博客对我有一定的启发https://www.cnblogs.com/zbtrs/p/6106783.html

总结了一下：

用数位DP的题目：

形如“问在x到y的整数中满足性质……的数的个数”

套路：

main函数一般是这样的

设max为上限值，即我们要统计 max之前的满足性质的数的个数

为了使搜到的数都满足 x<max

所以我们在搜索时定义一个bool型变量shangxian，表示搜到当前数位时前面的数位是否是沿着上限值

例如：上限max为54123

第一位时shangxian=true 搜0,1,2,3,4,5

若第一位搜到了0,1,2,3,4，下一位shangxian=false

若第一位搜到了5，下一位shangxian=true

若shangxian=false 该位枚举0~9，且向下递归时shangxian一直为false

若shangxian=true 该位枚举0~max[i],当该位搜到max[i]时，下一位shangxian=true，否则

Shangxian=false

windy数

显然这是一道数位DP的题

要注意的地方是前导全零时的状态转移

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define abs(i) ((i)>0?(i):(-i))
int a,b,maxx[],dp[][];//dp[i][j]前i位第i-1位是j的方案数
int dfs(int len,int lastnum,bool shangxian,bool O){
if(len==) return O^;
if(!shangxian&&dp[len][lastnum])
return dp[len][lastnum];
int cnt=,M=shangxian?maxx[len]:;
for(int i=;i<=M;i++){
if(!O&&abs(lastnum-i)<) continue;//前面都是前导0，该位不受其限制
cnt+=dfs(len-,i,shangxian&&i==M,O&&i==);
}
if(!shangxian&&!O) dp[len][lastnum]=cnt;//前面都是前导0，不会限制到下一位，不能记忆化
return cnt;
}
int solve(int x){
memset(maxx,,sizeof(maxx));
memset(dp,,sizeof(dp));//注意要清空数组
int k=;
while(x){
maxx[++k]=x%;
x/=;
}
return dfs(k,-,,);
}
int main()
{
scanf("%d%d",&a,&b);
printf("%d",solve(b)-solve(a-));
return ;
}