LOJ #10166. 「一本通 5.3 练习 1」数字游戏

题目：数字游戏

思路：数位dp

代码：

#include<bits/stdc++.h>
using namespace std;

int a,b,n;
int c[20];
int dp[20][200];

int dfs(int len,int sum,int limit) {
	if(len==0&&sum==0) return true;
	else if(len==0) return false;
	if(!limit&&(~dp[len][sum])) return dp[len][sum];
	int up=9;
	if(limit) up=c[len];
	int ans=0;
	for(int i=0;i<=up;i++) {
		ans+=dfs(len-1,(sum+i)%n,limit&&(i==c[len]));
	}
	if(!limit) dp[len][sum]=ans;
	return ans;
}

int slv(int x){
	memset(dp,-1,sizeof(dp));
	int len=0;
	while(x) {
		c[++len]=x%10;
		x/=10;
	}
	return dfs(len,0,true);
}

int main() {
	while(~scanf("%d%d%d",&a,&b,&n))
	printf("%dn",slv(b)-slv(a-1));
	return 0;
}

最后

以上就是优雅薯片为你收集整理的LOJ #10166. 「一本通 5.3 练习 1」数字游戏的全部内容，希望文章能够帮你解决LOJ #10166. 「一本通 5.3 练习 1」数字游戏所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。