【一本通提高数位动态规划】windy数

2021-06-10 11:05

阅读:574

标签:https   sizeof   res   lin   数位dp   onclick   ble   get   规划   

传送门【一本通提高数位动态规划】windy数

技术图片技术图片
#includeusing namespace std;
#define ll long long
ll dp[15][15],ans;
bool vis[15][15];
ll a[15];
ll l,r,len;
ll dfs(ll pos,ll pre,ll zero,ll limit)
{
    if(pos>len)return 1;
    if(!limit&&vis[pos][pre])return dp[pos][pre];
    ll res=limit?a[len-pos+1]:9,ret=0;
    for(int i=0;i)
    {
        if(abs(i-pre)2) continue;
        if(zero&&i==0) ret+=dfs(pos+1,-2,1,limit&&i==res);
        else ret+=dfs(pos+1,i,0,limit&&i==res);
    }
    if((!limit)&&(!zero))dp[pos][pre]=ret;
    vis[pos][pre]=1;
    return ret;
}
inline void get(ll x)
{
    len=0;
    while(x)a[++len]=x%10,x/=10;
}
int main()
{
    scanf("%lld%lld",&l,&r);
    get(r);
    ll ans=dfs(1,-2,1,1);
    memset(dp,0,sizeof dp);
    memset(vis,0,sizeof vis);
    get(l-1);
    ll ans1=dfs(1,-2,1,1);
    printf("%lld",ans-ans1);
}
数位DP

 数位DP详解

【一本通提高数位动态规划】windy数

标签:https   sizeof   res   lin   数位dp   onclick   ble   get   规划   

原文地址:https://www.cnblogs.com/yanghaokun/p/10605720.html


评论


亲,登录后才可以留言!