bzoj 1026 [SCOI2009]windy数（数位DP）

时间：2023-03-08 19:23:27

1026: [SCOI2009]windy数

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 4550  Solved: 2039
[Submit][Status][Discuss]

Description

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？

Input

包含两个整数，A B。

Output

一个整数。

Sample Input

【输入样例一】
1 10
【输入样例二】
25 50

Sample Output

【输出样例一】
9
【输出样例二】
20

HINT

【数据规模和约定】

100%的数据，满足 1 <= A <= B <= 2000000000 。

Source

【思路】

数位DP。

设f[i][j]表示i位数且最高位为j的数中windy数的个数。则有转移式：

f[i][j]=sigma{ f[i-1][k] } ( | j-k |>=2 )

统计：长度比len小的 -> 长度为len最高位比b[len]小的 -> 最高位为b[len]，统计方法见代码。

需要注意的是最后一项统计时，如果枚举过程中发现n不满足windy数则不再枚举，另外还需要注意n的计入与否。

【代码】

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int N = ;

 int f[N][N],b[N];

 void init() {

     for(int i=;i<;i++) f[][i]=;

     for(int i=;i<=;i++)

         for(int j=;j<;j++) {

             for(int k=;k<=j-;k++) f[i][j]+=f[i-][k];

             for(int k=j+;k<;k++) f[i][j]+=f[i-][k];

         }

 }

 int Fc(int n) {

     if(!n) return ;

     int ans=,len=,flag=;

     while(n)

         b[++len]=n% , n/=;

     for(int i=;i<len;i++)                                //统计所有长度小于 len 的

         for(int j=;j<;j++) ans += f[i][j];

     for(int j=;j<b[len];j++) ans += f[len][j];                //长度为 len 最高位比 b[len] 小的

     for(int i=len-;i;i--) {                            //统计最高位为 b[len] 的

         for(int j=;j<b[i];j++)

             if(abs(b[i+]-j)>=) ans += f[i][j];

         if(abs(b[i+]-b[i])<) {                        //n 不满足 不再统计后面的而且不计入 n

             flag=; break;

         }

     }

     if(flag) ans++;                                        //计入 n

     return ans;

 }

 int main() {

     int n,m;

     init();

     scanf("%d%d",&n,&m);

     printf("%d",Fc(m)-Fc(n-));

     return ;

 }

相关文章