求条C题数位dp,已拍出一组数据,玄二关
  • 板块学术版
  • 楼主miffy_123
  • 当前回复5
  • 已保存回复5
  • 发布时间2025/1/4 21:47
  • 上次更新2025/1/5 10:24:16
查看原帖
求条C题数位dp,已拍出一组数据,玄二关
705296
miffy_123楼主2025/1/4 21:47
#include <bits/stdc++.h>
#define int long long
#define rep(i,l,r) for(register int i(l);i^r+1;i=-(~i))
#define per(i,r,l) for(register int i(r);i^l-1;--i)
using namespace std;
int a[20],f[20][10];
int dfs(int now,bool limit,bool _0,int frst){
    if(!now)return (_0==0);
    if(!limit&&!_0&&frst>=0&&f[now][frst]!=-1){
        return f[now][frst];
    }
    int up=limit?min(a[now],frst-1):frst-1;
    if(frst==-1&&limit)up=a[now];
    if(frst==-1&&limit==0)up=9;
    int ans=0;
    rep(i,0,up){
        if(frst==-1&&i==0)ans+=dfs(now-1,0,1,-1);
        else if(frst==-1)ans+=dfs(now-1,i==up&&limit,i==0,i);
        else if(i==0)ans+=dfs(now-1,(0==up)&&limit,_0,frst);
        else ans+=dfs(now-1,limit&&i==up,0,frst);
    }
    if(!limit&&!_0&&frst>=0){
        return f[now][frst]=ans;
    }
    return ans;
}
int solve(int x){
    memset(a,0,sizeof(a));
    int tot=0;
    while(x){
        a[++tot]=x%10;
        x/=10;
    }
    memset(f,-1,sizeof(f));
    return dfs(tot,1,1,-1);
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int l,r;
    cin>>l>>r;
    cout<<solve(r)-solve(l-1);
    return 0;
}
输入:
178 883
正确输出:
203
2025/1/4 21:47
加载中...