昨天看了数位dp,虽然还是有点没懂不过水一发板子题先
这道题大概是数位dp的模板了,状态转移方程也比较显然。
设f[i][j]表示i位数,首位是j的windy数的数量,则容易有状态转移方程:f[i][j]=sum(f[i-1][k])(abs(j-k)>=2)
然后我们用这样几个循环先把这个f数组预处理一下(即在数据范围内的所有的windy数的数量)
for(int i=2;i<=10;i++) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) if(abs(j-k)>=2)f[i][j]+=f[i-1][k];
计算区间[A,B]内的windy数,可以考虑前缀和,求出[0,B]内的windy数和[0,A-1]内的windy数,然后相减输出。
对于求[0,B]区间内的windy数,设B有k位,考虑分为三段:
- 求出k-1位长的windy数
- 求出“k位长,首位小于B的最高位”的windy数
- 求出k位长,首位为B的最高位的windy数
这样就可以囊括完所有的部分
对于第三步,我们可以通过一个这样的过程来求解:
首先统计长度为k-1,最高位为i(0<=i<=B[k-1]-1)的windy数的数量,然后统计最高位是B[k-1]的windy数,特判一下若abs(B[i]-B[i-1])<2,则说明不符合条件,没有最高位为B[i],次高位是B[i-1]的windy数,就跳出循环。最后若i==1则说明还有windy数,统计的ans++。代码如下:
#includeusing namespace std;long long x,y;long long f[15][15];long long digit[15];void dp(){ memset(f,0,sizeof(f)); for(int i=0;i<=9;i++) //一位数都是windy数 f[1][i]=1; for(int i=2;i<=10;i++) //状态转移方程:f[i][j]=sum(f[i-1][k])(abs(j-k)>=2) for(int j=0;j<=9;j++) for(int k=0;k<=9;k++) if(abs(j-k)>=2)f[i][j]+=f[i-1][k];}long long solve(long long x){ memset(digit,0,sizeof(digit)); long long cnt=0,ans=0; if(x==0)return 0; while(x){ digit[++cnt]=x%10; x/=10; } for(int i=1;i<=cnt-1;i++) for(int j=1;j<=9;j++) ans+=f[i][j]; for(int i=1;i =1;i--){ for(int j=0;j<=digit[i]-1;j++) if(abs(j-digit[i+1])>=2)ans+=f[i][j]; if(abs(digit[i]-digit[i+1])<2)break; if(i==1)ans++; } return ans;}int main(){ scanf("%lld%lld",&x,&y); dp(); printf("%lld",solve(y)-solve(x-1)); return 0;}