Problem
有一机器人初始在 \(0\) 级阶梯,对于每一级阶梯,机器人可以从 \(1\sim N\) 种任选一个 \(i\) 走 \(A_i\) 步,同时有 \(M\) 个障碍在 \(B_i\) 级阶梯,若走到障碍则将无法移动,问能否通过某种方案使机器人到达第 \(X\) 级阶梯。
\(1\leq N\leq 10\),\(1\leq M\leq 10^5\),\(1\leq X\leq 10^5\),\(A_i\) 和 \(B_i\) 严格单调递增。
Solution
考虑使用动态规划(或可以直接称其为标记),设 \(f_i\) 为能否到达第 \(i\) 层阶梯。
那么初始状态为 \(f_0=1\),其它均为 \(0\)。
考虑到 \(N\) 最大仅为 \(10\),故可以在每层阶梯 \(i\) 直接枚举步数,若可以被之前的点走到(即 \(f_{i-A_j}=1\))则 \(f_i=1\),反之则 \(f_i=0\),最后判断 \(f_X\) 的值即可。
时间复杂度 \(\mathcal{O}(NX)\)。
Code
signed main(){
f[0]=1;
n=read();
F(i,1,n) a[i]=read();
m=read();
F(i,1,m) isTrap[read()]=1;
x=read();
F(i,a[1],x) // 直接从 a[1] 开始枚举,因为前面的点不可能会被更新,且 a[i] 严格单调递增,所以无需排序。
for (int j=1;j<=n&&i-a[j]>=0&&!f[i]&&!isTrap[i];++j) // 若枚举过程中已经使 f[i]=1 了,则无需再枚举。
f[i]=f[i-a[j]]&1;
puts(f[x]?"Yes":"No");
return 0;
}
标签:10,read,题解,机器人,Robot,阶梯,leq,枚举,ABC289D
From: https://www.cnblogs.com/reechee/p/17117936.html