题目大意
海里每一个位置都有一个深度,而且水里随着时间有锯齿状周期为 $2k$ 的潮汐。
当潮汐与深度之和大于给定值 $l$ 时 Koa 会溺水,游泳、海岸、岛上永远是安全的。
在任意时间 Koa 可以选择游到 $x+1$ 或停留在 $x$,试问 Koa 是否能够安全的从海岸 $0$ 到达岛上 $n+1$。
分析
开始的想法是随着时间 DP,更好的解法是贪心。
若一个位置在水位最高时仍不会溺水,则称这个位置是安全的,并且可以任意选择出发时机。
即安全位置之间是相互独立的,我们只需判断可达性,尽量到达每一个安全位置。若之后 $2k$ 个位置没有安全位置,必死。
Koa 的最优决策是在刚退潮时出发,如果能走就尽量往前走,不能走就等,等到涨潮就说明不存在通过方法。
int main() {
int ttt = rr();
while (ttt--) {
int n = rr(), k = rr(), l = rr();
int flag = 0;
int last = k;
for (ll i = 1; i <= n; i++) {
int d = rr();
flag += l < d;
if (l - d >= k)
last = k;
else
last = min(last - 1, l - d);
flag += abs(last) > l - d;
}
if (flag)
printf("No\n");
else
printf("Yes\n");
}
return 0;
}