[SCOI2009]windy数

梦里梦外; 2021-11-04 22:04 232阅读 0赞

### 题目描述 ###

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，

在A和B之间，包括A和B，总共有多少个windy数？

### 输入格式 ###

包含两个整数，A B。

### 输出格式 ###

一个整数

### 输入输出样例 ###

**输入 \#1**

1 10

**输出 \#1**

**输入 \#2**

25 50

**输出 \#2**

### 说明/提示 ###

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

【解题思路】

数位DP

数位dp一般解决的是一类数字问题：从l到r有多少个数符合某个性质，其中l和r都是很大的数，从l循环到r显然会TLE。

我们用f\[i\]\[j\]表示搜到第i位，上一位数是j的情况下的方案总数

第3位没有取到最大值，所以第4可以取到9

最后我们考虑限制条件：相邻两位绝对值大于等于2

如果前一位是前导000，那么我们不需要考虑这位0的绝对值，就是0和1也是可以取到的

所以我们可以在处理下一位时把这位当做−2处理

1 #include<bits/stdc++.h>
     2 using namespace std; 3 typedef long long ll; 4 ll dp[15][15],ans;//dp[i][j]表示搜到第i位，前一位是j，的！limit方案totnum；
     5 int a[15],len; 6 long long L,R; 7 ll dfs(int pos,int pre,int st,int limit)//pos当前位置,pre前一位数,st判断前面是否全是0,limit最高位限制 
     8 { 9     if(pos>len) return 1;//搜完了 
    10     if(!limit&&dp[pos][pre]!=-1) return dp[pos][pre];//没有最高位限制，已经搜过了
    11     ll ret=0; 12     int res=limit?a[len-pos+1]:9;//当前位最大数字 
    13     for(int i=0;i<=res;i++)//从0枚举到最大数字 
    14 { 15         if(abs(i-pre)<2) continue;//不符合题意，继续 
    16         if(st&&i==0) ret+=dfs(pos+1,-2,1,limit&&i==res);//如果有前导0，下一位随意 
    17         else ret+=dfs(pos+1,i,0,limit&&i==res);//如果没有前导0，继续按部就班地搜 
    18 } 19     if(!limit&&!st) dp[pos][pre]=ret;//没有最高位限制且没有前导0时记录结果 
    20     return ret; 21 } 22 void part(ll x) 23 { 24     len=0; 25     while(x) a[++len]=x%10,x/=10; 26     memset(dp,-1,sizeof dp); 27     ans=dfs(1,-2,1,1); 28 } 29 int main() 30 { 31     scanf("%lld%lld",&L,&R); 32     part(L-1);ll minn=ans; 33     part(R);  ll maxx=ans; 34     printf("%lld",maxx-minn); 35     return 0; 36 }

转载于:https://www.cnblogs.com/66dzb/p/11247120.html