Description
windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道,
在A和B之间,包括A和B,总共有多少个windy数?
Input
包含两个整数,A B。
Output
一个整数
Sample Input
【输入样例一】
1 10
【输入样例二】
25 50
1 10
【输入样例二】
25 50
Sample Output
【输出样例一】
9
【输出样例二】
20
9
【输出样例二】
20
HINT
【数据规模和约定】
100%的数据,满足 1 <= A <= B <= 2000000000 。
数位DP模板题
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int dp[15][15],a[15],l,r; int Dfs(int pos,int pre,bool zero,bool limit)//(当前位置,高一位的数是什么,是否含有前导零,当前位枚举时是否有上限限制) { if (pos==0) return 1; if (!limit && !zero && dp[pos][pre]) return dp[pos][pre]; int up=limit?a[pos]:9; int ans=0; for (int i=0;i<=up;++i) if (pre==10 || zero || i<=pre-2 || i>=pre+2) ans+=Dfs(pos-1,i,zero && i==0,limit && i==a[pos]); if (!limit && !zero) dp[pos][pre]=ans; return ans; } int Solve(int x) { int pos=0; while (x) a[++pos]=x%10,x/=10; return Dfs(pos,10,true,true); } int main() { scanf("%d%d",&l,&r); printf("%d",Solve(r)-Solve(l-1)); }