1026: [SCOI2009]windy数
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 8856 Solved: 4007
[Submit][Status][Discuss]
Description
windy界说了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包孕A和B，总共有几多个windy数？
Input
包罗两个整数，A B。
Output
一个整数
Sample Input【输入样例一】
1 10
【输入样例二】
25 50
【输出样例一】
9
【输出样例二】
20
【数据规模和约定】
100%的数据，满足 1 <= A <= B <= 2000000000
标题问题链接：
?id=1026
Solution觉得和数位DP很像。。。
mp [ i ] [ j ] 暗示 i 位数，以 j 为开头的windy数个数。。
这是可以预措置惩罚惩罚出来的。。
要求A,B之间的windy数个数，，只要分袂统计1~A-1和1~B的答案，然后相减即可。。。
代码
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> #define LL long long using namespace std; LL mp[15][15],a,b,c[15],d[15]; LL find(int x){ LL s=0; if(x==1){ for(int i=0;i<=d[x];i++) if(i-d[x+1]>=2||d[x+1]-i>=2) s+=mp[x][i]; return s; } for(int i=0;i<d[x];i++) if(i-d[x+1]>=2||d[x+1]-i>=2) s+=mp[x][i]; if(d[x]-d[x+1]>=2||d[x+1]-d[x]>=2) s+=find(x-1); return s; } LL get(LL x){ LL s=0; if(x>=0&&x<=9) return x; for(int i=1;i<=10;i++){ for(int j=1;j<=9;j++){ LL q=(j+1)*c[i]; if(x>=q) s+=mp[i][j]; } } LL z=x,js=0; while(z>0){d[++js]=z%10;z/=10;} s+=find(js-1); return s; } int main(){ c[1]=1; for(int j=0;j<=9;j++) mp[1][j]=1; for(int i=2;i<=10;i++) c[i]=c[i-1]*10; for(int i=2;i<=10;i++) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) if(j-k>=2||k-j>=2) mp[i][j]+=mp[i-1][k]; scanf("%lld%lld",&a,&b); a--; LL ans=get(b)-get(a); printf("%lld\n",ans); return 0; }
This passage is made by Iscream-2001.