数位dp/记忆化搜索

一、引例

#1033 : 交错和
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个数 x，设它十进制展从高位到低位上的数位依次是 a0, a1, ..., an - 1，定义交错和函数：

f(x) = a0 - a1 + a2 - ... + ( - 1)n - 1an - 1

例如：

f(3214567) = 3 - 2 + 1 - 4 + 5 - 6 + 7 = 4

给定 l, r, k，求在 [l, r] 区间中，所有 f(x) = k 的 x 的和，即：

1405402477702.png

输入
输入数据仅一行包含三个整数，l, r, k(0 ≤ l ≤ r ≤ 1018, |k| ≤ 100)。

输出
输出一行一个整数表示结果，考虑到答案可能很大，输出结果模 109 + 7。

提示
对于样例，满足条件的数有 110 和 121，所以结果是 231 = 110 + 121。

 1 /*
 2 ************************************交错和***********************************************
 3 ******************************by JA/C++ 2015-1-19****************************************
 4 */
 5 
 6 
 7 #include <cstdio>
 8 #include <cstring>
 9 long long mod = 1000000007;
10 long long base[20];
11 long long l, r, k, bit[20], bt, yy;
12 struct node {
13     long long s, n;//s代表数字和，n代表数字个数
14 };
15 node dp[20][400];//状态转移
16 node dfs(long long pos, long long target, long long limit)//数位dp，基本可以算是模板啦
17 {
18     node t;
19     t.s = t.n = 0;
20     if (pos == 0) {               //处理到最后一位，直接判断返回
21         if (target == 100)
22             t.n = 1;
23         return t;
24     }
25     if ((limit == 0) && (dp[pos][target].n != -1)) return dp[pos][target];
26     long long tail = limit ? bit[pos] : 9;
27     long long sgn = ((yy - pos) % 2) ? (-1) : (1);//确定符号
28     long long head;
29     if (pos == yy)head = 1;
30     else head = 0;//确定搜索的起点和终点
31     for (long long  i= head; i <= tail; i++)
32     {
33         node tmp = dfs(pos - 1, target - i*sgn, (limit == 1) && (i == bit[pos]));
34         if ((tmp.n)>0){
35             t.n += tmp.n;
36             long long q;
37             q = ((((tmp.n%mod)*base[pos]) % mod)*i) % mod;//结果的同余处理
38             t.s += (tmp.s) % mod;
39             t.s %= mod;
40             t.s += q;
41             t.s %= mod;//每一步都要同余
42         }
43     }
44     if (limit == 0) dp[pos][target] = t;
45     return t;
46 }
47 long long cal(long long x, long long y)
48 {
49     long long ans = 0;
50     if (x == -1) return 0;
51     if (x == 0) return 0;
52     bt = 0;
53     while (x)
54     {
55         bt++;
56         bit[bt] = x % 10;
57         x /= 10;
58     }
59     for (yy = 1; yy <= bt; yy++){
60         memset(dp, -1, sizeof dp);
61         ans += dfs(yy, y + 100, yy == bt).s;//对于每个长度为yy的数字进行处理
62         ans = (ans + mod) % mod;
63     }
64     return ans;
65 }
66 int main()
67 {
68     base[1] = 1;
69     for (int i = 2; i <= 19; i++)
70         base[i] = (base[i - 1] * 10) % mod;
71     scanf("%lld%lld%lld", &l, &r, &k);
72     //scanf_s("%lld%lld%lld", &l, &r, &k);
73     {
74         printf("%lld", (cal(r, k) - cal(l - 1, k) + mod) % mod);
75     }
76     return 0;
77 }

View Code

二、思路分析

给定取值范围，要求区间内数的交错和为给定数，需要用到数位dp,记忆搜索以及同余定理。

1.记忆化搜索写的时候要将相同交错和的个数，相同交错和的数字和分别进行dp。

2.对于一位数字和两位数字的计算方式并不相同，要分数字的位数进行讨论。

3.由于结果可能比较大，每一步都需要使用同余定理。

三、数位dp模板

 1 const int MAX_DIGITS, MAX_STATUS;
 2 LL f[MAX_DIGITS][MAX_STATUS], bits[MAX_DIGITS];
 3 
 4 LL dfs(int position, int status, bool limit, bool first)
 5 {
 6   if (position == -1)
 7     return s == target_status;
 8   if (!limit && !first && ~f[position][status])
 9     return f[position][status];
10   int u = limit ? bits[position] : MAX_BITS;
11   LL ret = 0;
12   for (int i = 0; i <= u; i++)
13   {
14     ret += dfs(position - 1, next_status(status, i), limit && i == u, first && !i);
15   }
16   return limit || first ? ret : f[pos][status] = ret;
17 }
18 
19 LL calc(LL n)
20 {
21   CLR(f, -1);
22   int len = 0;
23   while (n)
24   {
25     bits[len++] = n % 10;
26     n /= 10;
27   }
28   return dfs(len - 1, 0, true, true);
29 }
30 
31 int main()
32 {
33   //freopen("0.txt", "r", stdin);
34   LL a, b;
35   while (cin >> a >> b)
36     cout << calc(b) - calc(a - 1) << endl;
37   return 0;
38 }

四、记忆化搜索

记忆化搜索=搜索的形式+动态规划的思想

参考文献

1.算法合集之《浅谈数位类统计问题》——刘聪

2.推酷《数位dp模板》