题目传送门
题目描述
$windy$ 定义了一种 $windy$ 数. 不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 $windy$ 数.
$windy$ 想知道, 在 $A$ 和 $B$ 之间, 包括 $A$ 和 $B$, 总共有多少个 $windy$ 数?
输入格式
包含两个整数,$A,B$.
输出格式
输出一个整数, 表示答案.
样例
样例输入 1:
1 10
样例输出 1:
9
样例输入 2:
25 50
样例输出 2:
20
数据范围与提示
对于 $20%$ 的数据, 满足 $1\leqslant A\leqslant B\leqslant {10}^6$;
对于 $100%$ 的数据, 满足 $1\leqslant A\leqslant B\leqslant 2\times {10}^9$.
题解
一道数位 $DP$ 的板子题.
定义 $dp[i][j]$ 表示考虑到第 $i$ 位, 上一个数是 $j$ 的方案数.
搜索统计答案即可.
但是还需要注意两个点:
$alpha.$ 不能有前导 $0$, 搜索的时候打一个标记记一下就好了.
$beta.$ 搜索的时候不能超过那个数最高位的限制.
然而, 这并不是我想说的重点!!!
注意这两个代码的不同之处:
然而, 在洛谷上:
旋转懵逼~~~
自家 $OJ$ 上:
不过, 结局还是好的吧......
代码时刻
- #include<bits/stdc++.h>
- using namespace std;
- int A,B;
- int num[10];
- int dp[10][10];
- int dfs(int lent,int last,bool maxn,bool zero)
- {
- if(!lent)return 1;
- if(!maxn&&!zero&&dp[lent][last]!=-1)return dp[lent][last];
- int cnt=0,maxx=maxn?num[lent]:9;
- if(abs(last)>=2)
- if(zero)cnt+=dfs(lent-1,-20020923,maxn&&!maxx,1);
- else cnt+=dfs(lent-1,0,maxn&&!maxx,0);
- for(int i=1;i<=maxx;i++)
- if(abs(last-i)>=2)
- cnt+=dfs(lent-1,i,maxn&&(maxx==i),0);
- if(!maxn&&!zero)dp[lent][last]=cnt;
- return cnt;
- }
- int wzc(int x)
- {
- memset(dp,-1,sizeof(dp));
- num[0]=0;
- while(x)
- {
- num[++num[0]]=x%10;
- x/=10;
- }
- return dfs(num[0],-20020923,1,1);
- }
- int main()
- {
- scanf("%d%d",&A,&B);
- printf("%d",wzc(B)-wzc(A-1));
- return 0;
- }
- rp++
[BZOJ1026]:[SCOI2009]windy 数 (数位 DP)
来源: http://www.bubuko.com/infodetail-3146307.html