原题链接: 洛谷：点我QωQ bzoj：点我QωQ
定义一个 W i n d y Windy Windy数为：一个 W i n d y Windy Windy数没有前导零并且所有相邻的两位差的绝对值都 > = 2 >=2 >=2。给定 l , r l,r l,r求 [ l , r ] [l,r] [l,r]之间有多少 W i n d y Windy Windy数。
一行两个正整数 l , r l,r l,r。
l , r l,r l,r中有多少 W i n d y Windy Windy数。
输入 1 10 输出 9
输入 25 50 输出 20
显然数位 D P DP DP。我个人认为，数位 D P DP DP不难在 D P DP DP方程，而是难在数位拆分。
设 d p [ i ] [ j ] dp[i][j] dp[i][j]为：位长度为 i i i，首位是 j j j，有多少 W i n d y Windy Windy数。 那么 d p [ i ] [ j ] = d p [ i − 1 ] [ k ] ( ∣ k − j ∣ > = 2 ) dp[i][j]=dp[i-1][k]\quad(|k-j|>=2) dp[i][j]=dp[i−1][k](∣k−j∣>=2)，这很显然。也就是我们枚举一个满足条件的点作为上一个状态。
我们设一个 c a l c ( x ) calc(x) calc(x)，表示 [ 1 , x ] [1,x] [1,x]中有多少 W i n d y Windy Windy数。那么答案 = c a l c ( r ) − c a l c ( l − 1 ) =calc(r)-calc(l-1) =calc(r)−calc(l−1)。那么问题来了：如何求 c a l c ( x ) calc(x) calc(x)? 我们通过举例子的方法理解。设 x = 654 x=654 x=654。那么，答案分为几类呢？
首位是 [ 1 , 5 ] [1,5] [1,5]，剩下的位随便取。此时的答案是 d p [ 3 ] [ 1...5 ] dp[3][1...5] dp[3][1...5]位数 < 3 <3 <3。此时的答案为 d p [ 2 ] [ 1...9 ] + d p [ 1 ] [ 1..9 ] dp[2][1...9]+dp[1][1..9] dp[2][1...9]+dp[1][1..9]取 654 654 654的 1...3 1...3 1...3为前缀，剩下的位 < 654 <654 <654（即 6 ∗ ∗ 6** 6∗∗， 65 ∗ 65* 65∗， 654 654 654，其中 ∗ * ∗表示小于后面位的任意）。我们把它广义。设 x x x分解完有 c n t cnt cnt位，第 i i i位（全网为数不多的从左到右数的）为 d [ i ] d[i] d[i]。那么
也就是 d p [ c n t ] [ 1... ( d [ 1 ] − 1 ) ] dp[cnt][1...(d[1]-1)] dp[cnt][1...(d[1]−1)]也就是 d p [ 2... c n t ] [ 1...9 ] dp[2...cnt][1...9] dp[2...cnt][1...9]就比较复杂了，单独拿出来讲。我们枚举前缀长度 i i i从 1 1 1到 c n t − 1 cnt-1 cnt−1。枚举一个 j j j使得 ∣ j − d [ i ] ∣ > = 2 |j-d[i]|>=2 ∣j−d[i]∣>=2并且 j < d [ i + 1 ] j<d[i+1] j<d[i+1]。其中 ∣ j − d [ i ] > = 2 ∣ |j-d[i]>=2| ∣j−d[i]>=2∣保证满足条件， j < d [ i + 1 ] j<d[i+1] j<d[i+1]保证我们枚举出来的数 < = x <=x <=x。这样枚举 j j j后，加入 d p [ c n t − i ] [ j ] dp[cnt-i][j] dp[cnt−i][j]到答案。其中 c n t − i cnt-i cnt−i表示剩下 c n t − i cnt-i cnt−i位， j j j表示我们枚举剩下的首位为 j j j。当然，我们枚举的这个前缀要满足条件。即：如果 1... i 1...i 1...i中有差绝对值 < 2 <2 <2的就直接 b r e a k break break。当然，不用每次都查，只要在我们枚举 i i i的时候，判断下一次会不会 b r e a k break break即珂。当然还要特判 x x x。如果我们枚举的 i = = c n t − 1 i==cnt-1 i==cnt−1，说明搞完了，而且没有被 b r e a k break break掉，那么说明 x x x本身也是 W i n d y Windy Windy数，我们没有算到，故 + + a n s ++ans ++ans。
代码:
#include<bits/stdc++.h> using namespace std; namespace Flandle_Scarlet { #define N 20 int dp[N][N]; void DP() { for(int i=0;i<=9;++i) dp[1][i]=1;//明显边界 int n=11; for(int i=2;i<=n;++i) { for(int j=0;j<=9;++j) { for(int k=0;k<=9;++k) { if (abs(k-j)>=2) { dp[i][j]+=dp[i-1][k];//明显的转移 } } } } } int calc(int x) { int d[N];int cnt=0; while(x!=0) { d[++cnt]=x%10;; x/=10; }reverse(d+1,d+cnt+1);//我是正着数的,所以reverse int ans=0; for(int i=2;i<=cnt;++i)//情况2. { for(int j=1;j<=9;++j) { ans+=dp[cnt-i+1][j]; } } for(int i=1;i<d[1];++i)//情况1. { ans+=dp[cnt][i]; } for(int i=1;i<cnt;++i)//情况3. { for(int j=0;j<d[i+1];++j) { if (abs(d[i]-j)>=2) { ans+=dp[cnt-i][j]; } } if (abs(d[i]-d[i+1])<2) break; if (i==cnt-1) ++ans; } return ans; } void Main() { if (0) { freopen("","r",stdin); freopen("","w",stdout); } DP(); int l,r;scanf("%d%d",&l,&r); printf("%d\n",calc(r)-calc(l-1)); } }; main() { Flandle_Scarlet::Main(); return 0; }回到总题解界面
