首页 > 代码库 > [bzoj 1026]windy数(数位DP)

[bzoj 1026]windy数(数位DP)

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1026

分析:

简单的数位DP啦

f[i][j]表示数字有i位,最高位的数值为j的windy数总个数

那么f[i][j]=singma(f[i-1][k])(|j-k|>=2)

那么对于1~x(假设x从高到低的每位依次是x[n],x[n-1],……x[1])中的windy数个数就是f[n][0]+f[n][1]+……f[n][x[n]-1] + f[n-1][0]+f[n-1][1]+……f[n-1][x[n-1]-1] + ……

然后求a,b间的就一减就行了