2221 算法第二次练习赛题解

J - Malicious Mischance

题意

给定 $n$ 个硬币和他们出现的时间位置 $x_i, t_i$。初始时位于 $x=0$ 处，每一个周期仅能保持不动或向右移动一个单位。能够得到第 $i$ 个硬币当且仅当在 $t_i$ 个周期时位于 $x_i$，求能够获得的最多硬币个数。

题解

考虑从左向右、从早到晚处理所有的硬币。把所有硬币按照如此顺序排序，那么在处理 $coin_i$ 时能够取得的最大硬币个数就是在前面等待 $0,1,2,\cdots,t_i-x_i$ 个周期能够取得的最大硬币个数加一。 定义 $f[t-x]$ 为在前面等待 $t-x$ 个周期能够取得的最大硬币个数，$coin_i$ 对 $f$ 的贡献即为 $f[t_i-x_i]=max(f[0,1, \cdots,t_i-x_i])+1$，显然 $f$ 是可以被后面处理的硬币继承的。 注意离散化，用线段树取最大值即可。