我总是相信数位DP中DFS才是正解
有些操作可以看看我的另一篇题解
题目描述
由于科协里最近真的很流行数字游戏。
某人又命名了一种取模数,这种数字必须满足各位数字之和 mod N 为 0。
现在大家又要玩游戏了,指定一个整数闭区间 [a.b],问这个区间内有多少个取模数。
输入格式
样例
输入样例
1 9 19
输出样例
2
C++ 代码
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int dp[101][101];
int fj[101],cnt;
int a,b,n;
inline int dpp(int poi,int sy,bool lim) {
if(poi==0)
if(sy==0) return 1;
else return 0;
if(!lim&&dp[poi][sy]!=-1) return dp[poi][sy];
int maxx=lim? fj[poi]:9;
int ans=0;
for(int i=0; i<=maxx; i++)
ans+=dpp(poi-1,(sy+i%n+n)%n,lim&&i==maxx);
return lim? ans:dp[poi][sy]=ans;
}
int calc(int x) {
if(x==0) return 1;
cnt=0;
while(x) {
fj[++cnt]=x%10;
x/=10;
}
return dpp(cnt,0,1);
}
int main() {
while(scanf("%d%d%d",&a,&b,&n)!=EOF)
{
memset(dp,-1,sizeof dp);//标注-1可以呀,因为有可能dp值为1
printf("%d\n",calc(b)-calc(a-1));
}
return 0;
}
这个dp[i,j]定义的状态具体是什么呀
哈哈,我也相信数位DP中DFS才是正解
支持数位dp用dfs,+1
直接循环真-脑壳痛
%%%%
蟹蟹大佬
主要是没有Y老师那样的思维才选择DFS