1026: [SCOI2009]windy数
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
有好多美妙的细节，具体参见代码 O__O "…
#include<cstdio>
int A,B,ans;
int f[10][21],sum[21];
int l[21],len;
int Abs(int x){
return x<0?-x:x;
}
void PreTreatment(){
for (int i=0;i<10;++i)
f[i][1]=1;
sum[1]=9;
for (int k=2;k<10;++k){
for (int i=0;i<10;++i){
for (int j=0;j<10;++j)
if (Abs(i-j)>=2)
f[i][k]+=f[j][k-1];
if (i) sum[k]+=f[i][k];
}
}
for (int i=2;i<10;++i)
sum[i]+=sum[i-1];
for (int i=1;i<=2;++i)
for (int j=0;j<10;++j)
if (Abs(i-j)>=2)
f[i][10]+=f[j][9];
}
int calc(int x){
if (!x) return 0;
l[0]=233;
int res=1; len=0;
for (int k=x;k;k/=10){
l[++len]=k%10;
if (Abs(l[len]-l[len-1])<2)
res=0;
}
l[len+1]=233;
int ans=sum[len-1];
for (int k=len;k;--k){
for (int i=0;i<l[k];++i)
if ( ( k^len || i ) && Abs(l[k+1]-i)>=2 )
ans+=f[i][k];
if (Abs(l[k+1]-l[k])<2) break;
}
return ans+res;
}
int main(){
PreTreatment();
scanf("%d%d",&A,&B);
ans=calc(B)-calc(A-1);
printf("%d\n",ans);
}
评论 (0)
