数学与动态规划练习

2025-02-17 · 7 分钟阅读 · 算法数论动态规划 dfs 背包问题 ·

复制链接:

文章目录

题目来自 AcWing

1205. 买不到的数目 | 原题链接

首先说暴力做法。假设存在非负整数 $x,\space y$ 使得 $k=nx+my$。同时存在两组数非负整数 $(a_0,b_0)$ 与 $(a_1,b_1)$ 使得 $a_0n-b_0m=1,\space b_1m-a_1n=1$，这样可以得到 $k-1=(x-a_0)n+(y+b_0)m=(x+a_1)n+(y-b_1)m$。从大到小遍历 $k$ 时，第一个无法使 $x-a_0,\space y+b_0$ 或 $x+a_1,\space y-b_1$ 同时为正的 $k$ 即为所求值。

例如对样例中 $n=4,\space m=7$ 来说，$2\times4-1\times7=1,\space3\times7-5\times4=1$。当 $k=4x+7y,\space x,y\geq0$ 时，$k-1=4(x-2)+7(y+1)=4(x+5)-7(y-3)$。当 $k=18$ 时，$k=1\times4+2\times7$；而当 $k=17$ 时，$k=(-1)\times4+3\times7=6\times4+(-1)\times7$，无法满足条件。

根据上面的思路写出代码：

 1n, m = map(int, input().strip().split(" "))
 2if n > m:
 3    n, m = m, n
 4
 5i = 0
 6while True:
 7    if (i * m - 1) % n == 0:
 8        km = ((i * m - 1) // n, i)
 9        break
10    i += 1
11
12i = 0
13while True:
14    if (i * m + 1) % n == 0:
15        kn = ((i * m + 1) // n, i)
16        break
17    i += 1
18
19k = [0, n]
20for i in range(1, n * m)[::-1]:
21    if k[0] - kn[0] >= 0:
22        k[0] -= kn[0]
23        k[1] += kn[1]
24    elif k[1] - km[1] >= 0:
25        k[0] += km[0]
26        k[1] -= km[1]
27    else:
28        print(i)
29        break

经过观察发现，$k=18$ 能够表示而 $k=17$ 时不能够被表示，是因为 $1-2<0,\space 2-3<0$，推广后可以表示为 $k=nx+my,\space x-a_0<0,\space y-b_1<0$。那么当 $x-a_0=y-b_1=-1$ 时，$k$ 刚好不满足条件且最大，因此可以用 $(a_0-1)n+(b_1-1)m-1$ 来求出这个值。

 1n, m = map(int, input().strip().split(" "))
 2if n > m:
 3    n, m = m, n
 4
 5i = 0
 6while True:
 7    if (i * m - 1) % n == 0:
 8        km = ((i * m - 1) // n, i)
 9        break
10    i += 1
11
12i = 0
13while True:
14    if (i * m + 1) % n == 0:
15        kn = ((i * m + 1) // n, i)
16        break
17    i += 1
18
19print((kn[0] - 1) * n + (km[1] - 1) * m - 1)

这段代码也是能 AC 的。

DP 做法（同丑数）：

 1n, m = map(int, input().strip().split(" "))
 2
 3nums = [0]
 4nxtn = n
 5nxtm = m
 6ptrn = 0
 7ptrm = 0
 8while nums[-1] < n * m:
 9    nums.append(min(nxtn, nxtm))
10
11    if nums[-1] == nxtn:
12        ptrn += 1
13        nxtn = n + nums[ptrn]
14    if nums[-1] == nxtm:
15        ptrm += 1
16        nxtm = m + nums[ptrm]
17
18for i in range(1, len(nums))[::-1]:
19    if nums[i] - 1 != nums[i - 1]:
20        print(nums[i] - 1)
21        break

DFS 做法，带有记忆化搜索与剪枝：

 1n, m = map(int, input().strip().split(" "))
 2maximum = m * n
 3
 4
 5def dfs(current, result, maximum, n, m, memo):
 6    if current > maximum:
 7        return
 8
 9    if memo.get(current, False):
10        return
11    result.append(current)
12    memo[current] = True
13    dfs(current + n, result, maximum, n, m, memo)
14    dfs(current + m, result, maximum, n, m, memo)
15
16
17result = list()
18memo = dict()
19dfs(0, result, maximum, n, m, memo)
20result.sort()
21for i in range(1, len(result))[::-1]:
22    if result[i] - 1 != result[i - 1]:
23        print(result[i] - 1)
24        break

用数学方法来解决，这道题的本质是一个弗罗贝尼乌斯问题，又叫换钱问题，求解公式为 $pq-p-q$ 或 $(p-1)(q-1)-1$。

1print(*tuple(map(lambda x:(int(x[0]) - 1) * (int(x[1]) - 1) - 1, [input().strip().split(" ")])))

定理证明：AcWing 525. 小凯的疑惑

1211. 蚂蚁感冒 | 原题链接

这道题的一个关键点是，两只蚂蚁相遇后掉头也可以视为两只蚂蚁穿过对方。如果“零号病蚁”的前面没有蚂蚁与之相向而行，那么最终只会有他自己感染，因为他既无法追上前面的蚂蚁，他后面的蚂蚁也无法与他相遇。否则最终感染的蚂蚁是所有“指向”他的蚂蚁，即在他后面与之同向而行以及在他前面与之相向而行的蚂蚁，当然最后还要加上他自己。

 1n = int(input().strip())
 2ants = list(map(int, input().strip().split(" ")))
 3infected = ants[0]
 4ants.sort(key=abs)
 5
 6index = ants.index(infected)
 7
 8to_right = False
 9to_left = False
10left = 0
11right = 0
12for i in range(n):
13    if infected < 0 and i < index and ants[i] > 0:
14        to_right = True
15    elif infected > 0 and i > index and ants[i] < 0:
16        to_left = True
17    if i < index and ants[i] > 0:
18        left += 1
19    elif i > index and ants[i] < 0:
20        right += 1
21
22if infected > 0 and to_left or infected < 0 and to_right:
23    print(left + right + 1)
24else:
25    print(1)

1216. 饮料换购 | 原题链接

小学数学题。

1n = int(input().strip())
2count = n
3while n >= 3:
4    count += n // 3
5    n = n // 3 + n % 3
6print(count)

2. 01背包问题 | 原题链接

模板题，前几天刚练过01背包问题。

 1N, V = map(int, input().strip().split(" "))
 2val, wei = [0], [0]
 3for _ in range(N):
 4    vi, wi = map(int, input().strip().split(" "))
 5    wei.append(vi)
 6    val.append(wi)
 7
 8dp = [0 for _ in range(V + 1)]
 9
10for i in range(1, N + 1):
11    for j in range(wei[i], V + 1)[::-1]:
12        dp[j] = max(dp[j], dp[j - wei[i]] + val[i])
13
14print(dp[-1])

1015. 摘花生 | 原题链接

用 dp[i][j] 表示走到 $(i,j)$ 时能够采摘的最大的花生数量。又因为题目要求只能向右或向下走，因此只需要比较左侧和上侧的格子即可。状态转移方程为 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + field[i][j]

 1T = int(input().strip())
 2while T > 0:
 3    row, col = map(int, input().strip().split(" "))
 4    dp = [[0] * (col + 1)]
 5    for i in range(row):
 6        dp.append([0] + list(map(int, input().strip().split(" "))))
 7
 8    for i in range(1, row + 1):
 9        for j in range(1, col + 1):
10            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + dp[i][j]
11
12    print(dp[-1][-1])
13    T -= 1

895. 最长上升子序列 | 原题链接

使用 dp[i] 表示在第 $i$ 个位置时的最长上升子序列。状态转移方程为 dp[i] = max(dp[i], dp[j] + 1)，其中 j < i 且 nums[i] > nums[j]。

 1N = int(input().strip())
 2nums = list(map(int, input().strip().split(" ")))
 3dp = [1 for _ in range(N)]
 4
 5ans = 0
 6for i in range(N):
 7    for j in range(i):
 8        if nums[i] > nums[j] and dp[i] < dp[j] + 1:
 9            dp[i] = dp[j] + 1
10    ans = max(ans, dp[i])
11
12print(ans)

因为单独一个数的上升序列长度为 1，所以 dp 数组初始化为 1。

1212. 地宫取宝 | 原题链接

这题真难。多维 DP 都不简单，上一次是不开心的金明。

首先最容易想到的是一个深搜的写法：

 1MOD = 1000000007
 2n, m, k = map(int, input().strip().split(" "))
 3field = [[0] * (m + 1)]
 4for _ in range(n):
 5    field.append([0] + list(map(int, input().strip().split(" "))))
 6
 7
 8def dfs(i, j, cnt, val):
 9    if i > n or j > m or cnt > k:
10        return 0
11
12    if i == n and j == m:
13        if cnt == k:
14            return 1
15        elif cnt == k - 1 and field[i][j] > val:
16            return 1
17        else:
18            return 0
19
20    current = 0
21    current += dfs(i + 1, j, cnt, val) + dfs(i, j + 1, cnt, val)
22    current %= MOD
23    if field[i][j] > val:
24        current += dfs(i + 1, j, cnt + 1, field[i][j]) + dfs(i, j + 1, cnt + 1, field[i][j])
25        current %= MOD
26    return current
27
28
29ans = dfs(1, 1, 0, -1)
30print(ans)

这段深搜代码比较好理解，题目中的每一个限制条件在 dfs 函数中都有体现，美中不足的是这样做会超时，只能拿到 30% 的分数。所以还是要用动态规划解决。定义动态规划数组 dp[i][j][cnt][val] 表示在 $(i,j)$ 位置时手里有 $cnt$ 个物品且物品的最大价值为 $val$ 时的方法数。

对于每一个 dp[i][j][cnt][val]，其方法数可以来自两种情况数量的和：取或者不取。如果不取，则方法数为左一格和上一格中 $cnt$ 与 $val$ 和现在相等时的方法数，即 dp[i - 1][j][cnt][val] + dp[i][j - 1][cnt][val]。而如果取当前位置的宝物，那么方法数还要再加上左一格和上一格所有最大价值小于当前格物品的方法数，即 dp[i - 1][j][cnt - 1][v] + dp[i][j - 1][cnt - 1][v]，其中 $v<val$。

 1MOD = 1000000007
 2n, m, k = map(int, input().strip().split(" "))
 3field = [[0] * (m + 1)]
 4for _ in range(n):
 5    field.append([0] + list(map(lambda x: int(x) + 1, input().strip().split(" "))))
 6
 7dp = [[[[0 for _ in range(14)] for _ in range(k + 1)] for _ in range(m + 1)] for _ in range(n + 1)]
 8dp[1][1][0][0] = 1
 9dp[1][1][1][field[1][1]] = 1
10
11for i in range(1, n + 1):
12    for j in range(1, m + 1):
13        for cnt in range(k + 1):
14            for val in range(14):
15                dp[i][j][cnt][val] += dp[i - 1][j][cnt][val] + dp[i][j - 1][cnt][val]
16                dp[i][j][cnt][val] %= MOD
17
18                if val == field[i][j] and cnt > 0:
19                    for v in range(val):
20                        dp[i][j][cnt][val] += dp[i - 1][j][cnt - 1][v] + dp[i][j - 1][cnt - 1][v]
21                        dp[i][j][cnt][val] %= MOD
22
23ans = 0
24for value in dp[-1][-1][-1]:
25    ans += value
26print(ans % MOD)

注意

有些宝物的价值为 0，而将 dp 数组全部初始化为 0 的话会导致无法取到任何价值为 0 的宝物（当前宝物价值严格大于前面的宝物才可以取），因此将所有宝物的价值增加 1。因为题目要求方法数而不是总价值，所以增加的 1 不会影响结果。
dp[1][1][0][0] = 1 是指不取 $(1,1)$ 中宝物时的方法数为 1，此时取了 0 个宝物，最大价值为 0；dp[1][1][1][field[1][1]] = 1 是指取 $(1,1)$ 中宝物时的方法数为 1，此时取了 1 个宝物最大价值为 field[1][1] 即 $(1,1)$ 中宝物的价值。

1214. 波动数列 | 原题链接

又是一道动态规划题，不过在 DP 之前先分析一下。令数列 $p$ 的第一项为 $x$ 且 $p_{n+1}=d_n+p_n,d_n\in {a,-b}$，因此 $s=p_1+p_2+\cdots+p_n=x+(x+d_1)+(x+d_1+d_2)+\cdots+(x+d_1+d_2+\cdots+d_{n-1})=nx+(n-1)d_1+(n-2)d_2+\cdots+2d_{n-2}+d_{n-1}$。移项得到 $x=\frac{s-((n-1)d_1+(n-2)d_2+\cdots+2d_{n-2}+d_{n-1})}{n}$。因为 $x$ 一定为整数，因此 $n\mid s-((n-1)d_1+(n-2)d_2+\cdots+2d_{n-2}+d_{n-1})$，即 $s\equiv (n-1)d_1+(n-2)d_2+\cdots+2d_{n-2}+d_{n-1}\space(mod\space n)$。

此时令 dp[i][j] 表示已经选了 $i$ 个 $a$ 或 $-b$，此时满足数列的和同余 $j$ 模 $n$ 的方法数。因此 dp[i][j] 有两个来源：前一个数选择了 $a$ 或者前一个数选择了 $-b$。如果前一个数选择了 $a$，那么继承的方法数就是 dp[i - 1][(j - (n - i) * a) % n]。因为 $s$ 的同余类可以表示为 $\sum^n_{i=1}(n-i)d_i$，而当最后一次选择 $a$ 时 $d_i=a$，因此其前一项表示为 $j-(n-i)a$。同理，如果前一个数选择了 $b$，那么继承的方法数是 dp[i - 1][(j + (n - i) * b) % n]。

dp 数组只需要将 dp[0][0] 初始化为 1，表示当数列长度为 0 时，和为 0 只有一种方法：什么都没有。

 1MOD = 100000007
 2
 3n, s, a, b = map(int, input().strip().split(" "))
 4dp = [[0 for _ in range(n)] for _ in range(n)]
 5dp[0][0] = 1
 6
 7for i in range(1, n):
 8    for j in range(n):
 9        dp[i][j] = dp[i - 1][(j - (n - i) * a) % n] + dp[i - 1][(j + (n - i) * b) % n]
10        dp[i][j] %= MOD
11
12print(dp[n - 1][s % n])