2020ICPC·小米邀请赛 网络选拔赛第一场 A Intelligent Warehouse

从长度为$n$的序列$a$中取一些数, 要求两两满足倍数关系. 问最多取多少个数.

$1 \le n \le 2 \cdot 10^5, 1 \le a_i \le 10^7$

考虑dp, $dp(x)$表示取出来的数不超过$x$ 且一定取$x$, 最多能取的数量. ($10^7$的数组能开)

方程

$$dp(x) = cnt(x) + \max_{y | x} dp(y)$$

其中$cnt(x)$是$x$在$a$中出现的次数.

这可能就是一个"倍数关系转移"的思想吧, 这种题碰到的少, 要牢记.

$O(MAXA\log MAXA)$比较极限.

用类似埃筛的方法转移:

1
2
3
4
5

for (int x = 1; x <= maxa; x++) {
	dp[x] += cnt[x];	// 注意这里是 += , dp(x)的后半段已经算完了
	for (int j = 1; j <= prime_num, prime[j] * x <= maxa; j++)
		dp[prime[j] * x] = max(dp[prime[j] * x], dp[x]);
}

等于我们把$dp(x) = cnt(x) + \max_{y | x} dp(y)$的后半段先通过"前推"的方式转移, 然后到$x$的时候再加上前半段, 即$cnt(x)$

这样复杂度就稍微降低了一点, $O(MAXA \log \log MAXA)$

双倍经验: Codeforces Round #697 (Div. 3) G. Strange Beauty

cf这题$maxa \le 2 \cdot 10^5$, $O(MAXA \log MAXA)$ 的做法就能过

小米打完才知道是dp, 也没补, 今天看到cf这题发现好像哪里见过, 但是做不来, 于是赶紧补题写博客, 加强印象