本文主要是介绍(Nowcoder) E 诡异数字（数位dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
牛客小白月赛8真的打的自闭了，感觉一点都不小白 T_T (肯定是我太菜了，没错就是这样的)
题目链接https://www.nowcoder.com/acm/contest/214/E
题解说这是一个非常简单的数位dp，没接触过，感觉挺难的（大概这就是菜吧）
先稍微了解了一下数位dp，附上写的非常好的数位dp详解https://blog.csdn.net/wust_zzwh/article/details/52100392
然后看懂了大佬的代码，敲了一下再附上了我的理解
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=20020219;
const ll maxn=1e3+5;
ll lim[20],len[20];//lim分别记录每个数的最大重复次数，没有就置大
ll a[100][100][100];//len将数存入数组，每个位置也代表着上限
// pos pre num
// 记录着位数为pos(包括前导0，0012也算4位数)，前驱是pre，前驱重复数为num的满足条件的个数
// pos位的每一个位置的范围都是0-9，(就是代表完整的pos位数)
ll le,ri,n;
ll dfs(int pos,bool limit,int pre,int num){if(num>lim[pre]) return 0;//超过pre允许出现的最大次数，返回0 if(pos==0) return 1;// 0位返回1 if(!limit && a[pos][pre][num]!=-1) return a[pos][pre][num];//前驱不是上限，而且被更新过直接用 //如果前驱是上限，则后面上限也受到限制，不是一个完整的pos位，故不可用 int up=limit?len[pos]:9; //如果前驱达到上限，则这个位置的上限为解决数的上限ll sum=0;for(int i=0;i<=up;++i) {sum=(sum+dfs(pos-1,limit&&i==len[pos],i,i==pre?num+1:1))%mod;} return limit?sum:a[pos][pre][num]=sum;//前驱不是上限就更新，否则直接return
}ll solve(ll xx) {if(xx==-1) return 0;ll cnt=0;while(xx){len[++cnt]=xx%10;//每一位放入数组，cnt代表位数 xx/=10;}ll ans=0;for(int i=0;i<=len[cnt];++i){//最高位从0-len[cnt]枚举 ans=(ans+dfs(cnt-1,i==len[cnt],i,1))%mod;} return ans%mod;
}int main(){int T;scanf("%d",&T);while(T--){fill(lim,lim+11,0xffffffff);memset(a,-1,sizeof(a));scanf("%lld%lld%lld",&le,&ri,&n);ll xx,max_num;for(ll i=0;i<n;++i){scanf("%lld%lld",&xx,&max_num);lim[xx]=min(lim[xx],max_num);//更新 xx最大能出现lim[xx]次 }cout<<(solve(ri)-solve(le-1)+mod)%mod<<endl;}return 0;
}
这篇关于(Nowcoder) E 诡异数字（数位dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
