Codeforces Raif Round 1 G2. Lucky Numbers

有 $q$ 个询问每次询问的 $k$ 不变, 要求找到 $k$ 个非负数的和为 $n$. 如果这 $k$ 个数中某个数位 (个位, 十位, 百位…) 上有 $3, 6, 9$ 那么就会增加幸运值. 具体的数值如下表, $F$ 都会提前给出, 求出最大幸运值.

$1 \le n, k \le 999999, 1 \le F_i \le 10^9, 1 \le q \le 10^5$

能看出来和应该是一个背包(取一些数, 使其和为某值), 但明显不能直接背包, 因为这样复杂度至少 $O(k^2)$

注意到, 不同数字相同位置的数位交换对答案没有影响, 比如 $31, 29$ 和 $39, 21$ 对答案的贡献是一样的. 利用这个性质, 我们可以把 $k - 1$ 个数都构造成**仅由$0, 3, 6, 9$**组成(因为对答案的贡献为$0$, 所以可以含前导零), 而只剩下一个数, 可能有除 $0, 3, 6, 9$ 之外的其他数字. 也就是说, 能够构造出一种解, 使得最多只有一个数字, 每一位不全为 $0$ 或 $3$ 或 $6$ 或 $9$.

证明:

先只考虑某一位, 有两个数, 含有其他数字, 如 $\overline{a_0a_1 \dots a_x c}, \overline{b_0b_1 \dots b_x d}$.

1. 如果 $c + d \le 9$, 令 $e = c + d$, 那么可以变成 $\overline{a_0a_1 \dots a_x e}, \overline{b_0b_1 \dots b_x 0}$ 或者 $\overline{a_0a_1 \dots a_x 0}, \overline{b_0b_1 \dots b_x e}$

2. 如果 $c + d > 9$, 令 $f = c + d - 9$, 那么可以变成 $\overline{a_0a_1 \dots a_x 9}, \overline{b_0b_1 \dots b_x f}$ 或者 $\overline{a_0a_1 \dots a_x f}, \overline{b_0b_1 \dots b_x 9}$

这样, 本来我们需要对每一个选取的数字枚举所有至少含有$3, 6, 9$之一的所有数, 现在只需要对$k-1$个数字枚举仅含有$0, 3, 6, 9$的数. 剩下一个数字枚举所有数就行.

可是这样复杂度还是贼高.

每个数没有顺序, 各个数的每一位可以相互调换而不影响答案, 这就表示了, 实际上不需要把所有数是什么都求出来. 并且发现, 对于特定的一位, 6的价值是3的$2$倍, 9的价值是3的$3$倍, 再加上之前我们搞了一个0过来, 0的价值是3的$0$倍.

可以这样想, 对于特定的一位, 我们有 $3(k-1)$ 个3可以选择, 比如个位数选了 $3$ 个 3, 要求选两个数, 那么可以是 $0, 9$, 或者 $3, 6$等等. 这样我们就可以对每一位用一个需要装满的01背包来做了. 直接背包的话 $6 \times 3k$ 数量级稍大. 由于每个物品(3)重量和价值一模一样, 可以用二进制拆分.

然后还剩下一个数字, 我们对每一位直接枚举, 更新同一个dp值即可.

复杂度 $O(k + q)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

const int MAXN = 1e6+10;

int n, q, k, N = 999999;
LL dp[MAXN], F[10], power[10] = {1, 10, 100, 1000, 10000, 100000};

int main() {
	scanf("%d", &k);
	for (int i = 0; i < 6; i++)
		scanf("%lld", F + i);
	for (int i = 1; i <= N; i++)
		dp[i] = -INF;
	dp[0] = 0;
	for (int d = 0; d < 6; d++) {
		for (LL i = 3 * (k - 1), e = 1; i; i -= e, e <<= 1) {
			e = min(e, i);
			LL w = e * power[d] * 3;
			LL v = e * F[d];
			for (LL j = N; j >= w; j--)
				dp[j] = max(dp[j], dp[j - w] + v);
		}
	}
	for (int d = 0; d < 6; d++)
		for (LL j = N; j; j--)
			for (int a = 0; a < 10; a++) {
				LL w = power[d] * a;
				LL v = a % 3 ? 0 : a / 3 * F[d];
				if (j >= w)
					dp[j] = max(dp[j], dp[j - w] + v);
			}
	scanf("%d", &q);
	while (q--) {
		scanf("%d", &n);
		printf("%lld\n", dp[n]);
	}
	return 0;
}