返回信息流Description
Two lovely frogs Alice and Bob live by a river. There are several stones in this river. Every morning, they will go to the other side of the river to have fun. They cross the river by jumping from one stone to another. One day, Alice decides to play tricks on Bob. She plans to remove some stones so that there is no “easy jump” for Bob to across the river any more. But she has no idea which stones she should remove. She needs your help.
The width of the river is an integer L((1≤L≤1,000,000,000). We treat the river as a one-dimensional line segment,with two endpoints A (two frog’s home) and B (the other side of the river). Among the river, there are N stones (0≤N≤50,000). The distance from the i-th stone to side A is Di (0<Di<L). Alice would like to remove M stones in the river (0≤M≤N) so that with the rest of the stones, the minimum distance among all possible jumps for Bob is the largest.
Input
Each instance contains two lines. The first line contains three integers L, N and M. The second line gives the positions of M stones. No two stones share the same position.
30% test cases guarantee that N < 20.
Output
For each instance, output a single line with a single integer which is the maximum of the minimum distance among all possible jumps after removing M stones. In the example, Alice should remove stones with distance 2 and 14. After removing these two stones, the minimum distance of jumps is 4, and there are two jumps with distance 4: from 17 to 21, and from 21 to 25.
Sample Input
25 5 2
2 14 11 21 17
Sample Output
4
也救救这个孩子吧！
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #96867同步于 2018/10/19
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】大神们，动态规划问题，也救救这个孩子吧
LittleHorse
2018/10/19镜像同步7 回复
订阅后，新回复会通过你的通知中心匿名送达。
7 条回复
【 在 curiosity 的大作中提到: 】
: 题目信息不全哪。样例解释得更是一塌糊涂
谢谢大佬，不好意思，我补充上了Sample Input和Sample Output
【 在 ytz123 的大作中提到: 】
: 直接二分答案吧，judge函数直接贪心应该没有问题，为啥要dp呢
是刚讲完dp然后发了这个题...所以想用dp
DP的话有个空间复杂度O(n^2)，时间复杂度O(n^3)的DP
你先把左右两个端点看成两个不可删去的石头，这样就有n+2个石头，标号为1,2,3...n+2
状态dp[i][j]代表到第i个石头，第i个石头不删去，并且前面已经删去了j个石头的情况下
前i个石头剩下的石头中的maximum of the minimum distance
那么dp[n + 2][m]就是答案
转移方程就dp[i][j] = max(dp[i][j], min(a[i] - a[i - 1 - (j - k)], dp[i - 1 - (j - k)][k]))
dp数组的初始化和转移边界自己思考
当然这个dp是不能解决所有数据的，抛砖引玉
(明明二分可以做，却因为刚学了dp就要用dp说实话...算了不说实话了嘻嘻)