數位dp,dp[i][j][k],
i表示3類數字:
1類表示windy,0類表示當前所有windy數,0類表示以0開頭的windy但加上前導零就不是windy的數,2類表示除了0類以外的windy
j范圍0~9,表示以j開頭的windy數。
k表示位數
j表示以0~9開頭的數字
#include<stdio.h> #include<string.h> #define LL long long int dp[3][11][30];//1表示windy,0表示以0開頭的windy但加上前導零就不是windy的數,2表示除了0類以外的windy int a[15]; void init() { int i,j,k; for(i=0;i<10;i++)dp[1][i][1]=1; dp[2][0][1]=1; for(i=2;i<12;i++){ for(j=0;j<10;j++){ if(j==0){ for(k=0;k<10;k++){ dp[1][j][i]+=dp[1][k][i-1];//以0開頭的,把前面所有的windy都加上去 if(k>=2)dp[2][j][i]+=dp[1][k][i-1];//以0開頭的,處理出2類 } continue; } for(k=0;k<10;k++) { if(j-k>=2||j-k<=-2){ if(k) dp[1][j][i]+=dp[1][k][i-1];//沒有前導零 else dp[1][j][i]+=dp[2][k][i-1];//k=0,有前導零,要把0類去掉 } } } } } int solve(int n) { int i,j,k; for(i=1;n;i++) { a[i]=n%10; n/=10; } int len=i,ans=0; a[len]=-2; for(i=len-1;i>0;i--) { for(j=0;j<a[i];j++) { if(j-a[i+1]>=2||j-a[i+1]<=-2) { if(j==0&&i<len-1){ ans+=dp[2][j][i]; continue; } ans+=dp[1][j][i]; } } if((a[i]-a[i+1]<2)&&(a[i]-a[i+1]>-2))break; } return ans; } int main() { init(); int a,b; while(scanf("%d%d",&a,&b)!=-1) printf("%d\n",solve(b+1)-solve(a)); return 0; } //123123 3245355