[BZOJ1026] windy数

Description

求 ([a,b]) 之间相邻数位只差不超过 (2) 的数字个数。(a,b le 2 imes 10^9)。

Solution

设 (f[i][j][k]) 表示从高到低走了 (i) 位，第 (pos) 位是 (j)，且当前数字与 (n) 的关系为 (k)（(1) 表示等于，(0) 表示小于）

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 25;

int f[N][N][N],a[N],n;

// 表示从高到低走完了第 i 位，第 i 位是 j，且当前数字与 n 的关系为 k（1 表示等于，0 表示小于）
int dfs(int i,int j,int k)
{
    if(~f[i][j][k]) return f[i][j][k];
    if(i==0) return f[i][j][k]=1;
    int lim = k?a[i-1]:9, ans = 0;
    if(j==-1)
    {
        for(int p=1;p<=lim;p++) ans+=dfs(i-1,p,p==lim);
    }
    else
    {
        for(int p=0;p<=min(j-2,lim);p++) ans+=dfs(i-1,p,k&&p==lim);
        for(int p=j+2;p<=lim;p++) ans+=dfs(i-1,p,k&&p==lim);
    }
    return f[i][j][k]=ans;
}

int solve(int val)
{
    memset(a,0,sizeof a);
    n=0;
    while(val)
    {
        a[n++]=val%10;
        val/=10;
    }
    memset(f,0xff,sizeof f);
    if(n==0) return 0;
    return dfs(n,-1,1);
}

int calc(int val)
{
    int ans = solve(val);
    int tmp = 1;
    while(tmp*10<=val) tmp*=10;
    --tmp;
    while(tmp)
    {
        ans += solve(tmp);
        tmp /= 10;
    }
    return ans;
}

signed main()
{
    ios::sync_with_stdio(false);

    int a,b;
    cin>>a>>b;
    --a;

    cout<<calc(b)-calc(a)<<endl;

    return 0;
}