牛客月赛8-诡异数字-(数位dp)

E

题意：
就是每次给你n个限制，每个限制就是数字a连续出现的次数不能大于b，然后在这n个限制的条件下，l到r区间的内满足的一共有多少数。

思考：
就是数位dp的裸题，当时不知道怎么想的，还想去维护每一位的连续出现次数啥的，其实仅仅维护上一位pre和连续出现的次数cnt就行了，因为每多一位状态就全部更新了，然后判断是否>b，然后记忆化就行了。
其实呢对于dp里面对limit和lead这两维的限制无所谓，主要是pre，cnt，suc，这种状态类型的，一定要多加几维。

代码：

int T,n,m;
int va[N];
int vb[N];
int dp[20][10][20][2];int dfs(int pos,int limit,int lead,int pre,int cnt,int suc)
{if(!pos) return !suc;if(!limit&&!lead&&dp[pos][pre][cnt][suc]!=-1)return dp[pos][pre][cnt][suc]%mod;int res = 0;int up = limit?va[pos]:9;for(int i=0;i<=up;i++){int limit_t = limit&&(i==up);int lead_t = lead&&(i==0);int suc_t = suc;int cnt_t = (i==pre)?cnt+1:1;if(cnt_t>vb[i]) suc_t = 1;res = (res+dfs(pos-1,limit_t,lead_t,i,cnt_t,suc_t))%mod;}if(!limit&&!lead) dp[pos][pre][cnt][suc] = res%mod;return res%mod;
}int f(int x)
{mem(dp,-1);int pos = 0;while(x) va[++pos] = x%10,x/=10;return dfs(pos,1,1,0,0,0)%mod;
}signed main()
{IOS;cin>>T;while(T--){int l,r,n;cin>>l>>r>>n;for(int i=0;i<=9;i++) vb[i] = inf;for(int i=1;i<=n;i++){int a,b;cin>>a>>b;vb[a] = min(vb[a],b);}if(l==0) cout<<f(r)%mod<<"\n";else cout<<(f(r)-f(l-1)+mod)%mod<<"\n";}return 0;
}

总结：
多思考思考，多加几维限制。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！