数字游戏（数位dp）

WA_Code:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 15;
 5 const int mod = 1e9+7;
 6 
 7 ll l,r;
 8 int n;
 9 int a[15];
10 ll dp[15][15];
11 
12 ll dfs(int pos,int pre,int sum, bool lead, bool limit){
13     if( !pos ) return sum==0;
14     if( !limit && !lead && dp[pos][pre]!=-1 ) return dp[pos][pre];
15 
16     int up=limit?a[pos]:9;
17     ll ans = 0;
18     for(int i=0;i<=up;i++){
19         ans += dfs(pos-1,i,(sum+i)%n,lead&&!i, limit&&(i==up));
20     }
21     return (!limit&&!lead)?dp[pos][pre]=ans:ans;
22 }
23 
24 ll solve(ll x){
25     a[0] = 0;
26     while( x ) a[++a[0]]=x%10, x/=10;
27     return dfs(a[0],0,0,1,1);
28 }
29 
30 int main()
31 {
32 
33     while( ~scanf("%lld%lld%d",&l,&r,&n)){
34         memset(dp,-1,sizeof(dp));
35         printf("%lld
",solve(r)-solve(l-1));
36     }
37     return 0;
38 }

AC_Code:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 15;
 5 const int mod = 1e9+7;
 6 
 7 ll l,r;
 8 int n;
 9 int a[15];
10 ll dp[15][110];
11 
12 ll dfs(int pos,int pre,int sum, bool lead, bool limit){
13     if( !pos ) return sum==0;
14     if( !limit && !lead && dp[pos][sum]!=-1 ) return dp[pos][sum];
15 
16     int up=limit?a[pos]:9;
17     ll ans = 0;
18     for(int i=0;i<=up;i++){
19         ans += dfs(pos-1,i,(sum+i)%n,lead&&!i, limit&&(i==up));
20     }
21     return (!limit&&!lead)?dp[pos][sum]=ans:ans;
22 }
23 
24 ll solve(ll x){
25     a[0] = 0;
26     while( x ) a[++a[0]]=x%10, x/=10;
27     return dfs(a[0],0,0,1,1);
28 }
29 
30 int main()
31 {
32 
33     while( ~scanf("%lld%lld%d",&l,&r,&n)){
34         memset(dp,-1,sizeof(dp));
35         printf("%lld
",solve(r)-solve(l-1));
36     }
37     return 0;
38 }

AC代码和WA代码的不同之处在于：

WA: dp[pos][pre]:枚举到第pos位,前一个数是pre的满足题意的个数
AC: dp[pos][sum]:枚举到第pos位,前几位的和是sum的满足题意的个数

写这篇博客主要是想告诉自己dp不是怎么设都可以的，题目要求啥才设啥

这道题目跟pre没有直接关系，而是跟sum有关系