T3_颗秒 题解 特殊性质 A:\tt{A:}A: 得分型性质。 s=1s=1s=1，每秒有三种走法。分别是左转 111，不旋转，右转 111。也即 nnn 秒共有 3n3^n3n 种不同的旋转方式。由于 n≤10n\le 10n≤10，考虑爆搜，时间复杂度：O(3n)O(3^n)O(3n) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 测试点 4∼10(AC)4\sim 10(\tt{AC})4∼10(AC) 考虑 dpdpdp。定义 dpidp_idpi 表示考虑前 iii 个靶子，且必须击中第 iii 秒的靶子的情况下最多能击中的靶子数。 初始状态 dp0=0dp_0=0dp0 =0 注意到 n≤2×103n\le 2\times 10^3n≤2×103，考虑 n2n^2n2 转移。 定义 dis(i,j)dis(i,j)dis(i,j) 表示 i,ji,ji,j 之间的距离，计算如下 如果要考虑击中第 jjj 秒的靶子然后击中第 iii 秒的靶子： * 速度：每秒 sss 个单位 * 距离：dis(ai,aj)dis(a_i,a_j)dis(ai ,aj ) * 时间：i−ji-ji−j 显然如果距离 ≤\le≤ 速度 ×\times× 时间，并且第 jjj 个靶子是可达的，那么可以转移 dpi=max⁡(dpi,dpj+1)dp_i=\max(dp_i,dp_j+1)dpi =max(dpi ,dpj +1)。 这个可达是一个坑点，由于击中 000 个靶子也是一种状态，所以 dpdpdp 不能赋 000 值。 做完了，答案即为 maxi=1ndpimax_{i=1}^n dp_imaxi=1n dpi 。 时间复杂度：O(tn2)O(tn^2)O(tn2)