[SCOI2009]windy数
2021-02-12 22:15
阅读：589
题目描述
windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，
在A和B之间，包括A和B，总共有多少个windy数？
输入输出格式
输入格式：包含两个整数，A B。
输出格式：一个整数
输入输出样例
输入样例#1：
复制
1 10
输出样例#1： 复制
9
输入样例#2： 复制
25 50
输出样例#2： 复制
20
说明
100%的数据，满足 1
数位dp裸题，记忆化搜索
要判断前导0
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 int f[21][11],s[21]; 8 int dfs(int pos,int pre,int k,int flag) 9 {int i; 10 if (pos==0) return 1; 11 if (k&&!flag&&f[pos][pre]!=-1) return f[pos][pre]; 12 int ed=9,cnt=0; 13 if (flag) ed=s[pos]; 14 for (i=0;i) 15 if (pre==-1||abs(i-pre)>=2) 16 { 17 if (k==0&&i==0) cnt+=dfs(pos-1,-1,0,flag&&(i==ed)); 18 else 19 cnt+=dfs(pos-1,i,k|(i!=0),flag&&(i==ed)); 20 } 21 if (!flag&&k) f[pos][pre]=cnt; 22 return cnt; 23 } 24 int solve(int x) 25 { 26 memset(f,-1,sizeof(f)); 27 int len=0; 28 if (x==0) return 1; 29 while (x) 30 { 31 s[++len]=x%10; 32 x/=10; 33 } 34 return dfs(len,-1,0,1); 35 } 36 int main() 37 {int A,B; 38 cin>>A>>B; 39 printf("%d",solve(B)-solve(A-1)); 40 }
评论
亲，登录后才可以留言！