Windy数BZOJ 数位DP

#include<iostream>
#include<cstdio>
#include<cstring>
int qqq(int x)
{
    return x>=0?x:-x;
}
using namespace std;
int dp[15][10][2];
char a[15],b[15];
int main()
{
    scanf("%s%s",a+1,b+1);
    int ans=0;
    int x=strlen(a+1);
    if(a[1]=='1'&&x==1)
        ans++;
    int q=x;
    while(a[q]=='0')
    {
        a[q]='9';
        q--;
    }
    a[q]-=1;
    int y=strlen(b+1);
    for(int i=1;i<b[1]-'0';i++)
        dp[1][i][0]=1;
    dp[1][b[1]-'0'][1]=1;
    for(int i=2;i<=y;i++)
    for(int j=1;j<=9;j++)
        dp[i][j][0]=1;

    for(int i=1;i<=y;i++)
    for(int j=0;j<=9;j++)
    for(int k=0;k<=9;k++)
    {
        if(qqq(j-k)>=2)
        {
            dp[i][j][0]+=dp[i-1][k][0];
            if(j<b[i]-'0'&&k==b[i-1]-'0')
                dp[i][j][0]+=dp[i-1][k][1];
            if(j==b[i]-'0'&&k==b[i-1]-'0')
                dp[i][j][1]+=dp[i-1][k][1];
        }
    }
    for(int i=0;i<=9;i++)
    {
        ans+=dp[y][i][0];
        ans+=dp[y][i][1];
    }
    memset(dp,0,sizeof(dp));
    for(int i=1;i<a[1]-'0';i++)
        dp[1][i][0]=1;
    dp[1][a[1]-'0'][1]=1;
    for(int i=2;i<=x;i++)
    for(int j=1;j<=9;j++)
        dp[i][j][0]=1;
    for(int i=1;i<=x;i++)
    for(int j=0;j<=9;j++)
    for(int k=0;k<=9;k++)
    {
        if(qqq(j-k)>=2)
        {
            dp[i][j][0]+=dp[i-1][k][0];
            if(j<a[i]-'0'&&k==a[i-1]-'0')
                dp[i][j][0]+=dp[i-1][k][1];
            if(j==a[i]-'0'&&k==a[i-1]-'0')
                dp[i][j][1]+=dp[i-1][k][1];
        }
    }
    for(int i=0;i<=9;i++)
    {
        ans-=dp[x][i][0];
        ans-=dp[x][i][1];
    }
    printf("%d",ans);
    return 0;