无
无
无
无
CF 659 B2 Koa and the Beach (Hard Version) https://codeforces.com/contest/1384/problem/B2
题意 需要从海滩游到海岛上,给定初始时波浪高度等于0时的水深分布,波浪高度在0-k-0-k之间连续变动,已知最深能够游的水深D,求是否可以游到小岛
题解 设波浪高度为k-0-k,维护到达位置i时,可能的波浪时间范围[l, r]。位置i+1时,波浪的范围为[l+1, r+1]和 [k - (D - d[i]), k + (D - d[i])]的交,如果长度为0则不可游到。特别的,如果D大于d[i]+k则时间范围为[0,2k-1],即整个长度
特别要注意D - d[i]小于0的情况。这里pretest没有测结果B2 System test的时候WA了
Tag dp
Comment 这道题需要基于位置思考,而不是基于时间思考,因为波浪的变化是周期性有规律的,便于处理,而水深的变化是任意的。