[SCOI2009]WINDY数 题解

记录一下当前数和前导0即可，相邻两数位之差绝对值小于2的方案直接忽略不计。
五分钟AC解决战斗。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[20];
int f[20][12][2];
int dp(int pos,int num,bool leg,bool flag)
{
    if(pos==0) return 1;
    if(flag&&f[pos][num][leg]!=-1) return f[pos][num][leg];
    int x=flag?9:a[pos];
    int ans=0;
    for(int i=0;i<=x;i++)
    {
        if(leg&&abs(i-num)<2) continue;
        ans+=dp(pos-1,i,leg||i,flag||i<x);
    }
    if(flag) f[pos][num][leg]=ans;
    return ans;
}
int cul(int x)
{
    int pos=0;
    while(x)
    {
        a[++pos]=x%10;
        x/=10;
    }
    return dp(pos,0,0,0);
}
signed main()
{
    memset(f,-1,sizeof(f));
    int l,r;
    scanf("%lld%lld",&l,&r);
    printf("%lld\n",cul(r)-cul(l-1));
}