BZOJ_1026_[SCOI2009]windy数_数位DP

2021-02-13 21:15

阅读：448

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

学一下数位DP。

f[i][j]表示i位数以j开头的windy数个数。转移有f[i+1][k]+=f[i][j](abs(j-k)>=2)

答案转成[1~R]-[1~L-1]之后按位枚举，每次枚举到当前位上的数减1。

注意：

1.枚举到两位差2以内时停止枚举。

2.答案要加上位数比他小的所有windy数。

代码：

 1 #include  2 #include string.h>
 3 #include 
 4 using namespace std;
 5 int f[15][15],a,b;
 6 int c[15],d[15];
 7 int sol(int x){
 8     int num=x,cnt=0,ans=0;
 9     while(num){
10         c[++cnt]=num%10;
11         num/=10;    
12     }for(int i=1;i1];
13     for(int i=1;i)    
14         for(int j=1;j9;j++)ans+=f[i][j];
15     for(int i=1;i1];i++)ans+=f[cnt][i];
16     for(int i=2;i){
17         for(int j=0;j){
18             if(d[i-1]-j2&&j-d[i-1]2)continue;
19             ans+=f[cnt-i+1][j];
20         }
21         if(d[i-1]-d[i]2&&d[i]-d[i-1]2)break;
22     }
23     return ans;
24 }
25 int main(){
26     for(int i=0;i9;i++)f[1][i]=1;
27     for(int i=2;i10;i++){
28         for(int j=0;j9;j++){
29             for(int k=0;k9;k++){
30                 if(k-j2&&j-k2)continue;
31                 f[i][j]+=f[i-1][k];
32             }
33         }
34     }
35     scanf("%d%d",&a,&b);
36     //sol(18717);
37     printf("%d\n",sol(b+1)-sol(a));
38 }
39 /*
40 18716
41 38434
42 
43 5178*/

上一篇：WPF中的数据验证

下一篇：BZOJ_1179_[Apio2009]Atm_tarjan+spfa

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：BZOJ_1026_[SCOI2009]windy数_数位DP
文章链接：http://soscw.com/essay/54966.html

亲，登录后才可以留言！

BZOJ_1026_[SCOI2009]windy数_数位DP

评论

热门文章

推荐文章

最新文章

置顶文章