?id=1026 (题目链接)
题意在区间${[A,B]}$有多少个数相邻两个数位上的数之差至少为2。
Solution数位dp，右转题解：LCF
其中${f[i][0]}$，表示的是第${i}$位为${0}$的方案数，并不是不取${i}$位。
细节LL
代码// bzoj1026 #include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<cmath> #include<ctime> #define LL long long #define inf (1ll<<30) #define MOD 1000000007 #define Pi acos(-1.0) #define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); using namespace std; LL f[20][10],g[20],ans; int n,a[2],t[20]; LL solve(int p) { memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); for (n=0;a[p];a[p]/=10) t[++n]=a[p]%10; for (int i=0;i<10;i++) f[1][i]=1; for (int i=2;i<=n;i++) for (int j=0;j<10;j++) for (int k=0;k<10;k++) if (abs(j-k)>1) f[i][j]+=f[i-1][k]; g[1]=1; for (int i=2;i<=n;i++) { for (int j=0;j<t[i-1];j++) if (abs(t[i]-j)>=2) g[i]+=f[i-1][j]; if (abs(t[i]-t[i-1])>1) g[i]+=g[i-1]; } LL res=0; for (int i=1;i<n;i++) for (int j=1;j<10;j++) res+=f[i][j]; for (int i=1;i<t[n];i++) res+=f[n][i]; return res+g[n]; } int main() { scanf("%d%d",&a[0],&a[1]);a[0]--; ans-=solve(0); ans+=solve(1); printf("%lld",ans); return 0; }
【bzoj1026】 SCOI2009—windy数
，