题解 P6398 【[COI2008] KOLEKCIJA】
louhao088
·
·
题解
思路
动态规划
方法
先将这m个数字从小到大排序。
那么$F_i=min${$F_j+max${$k,A_i-A_j+1+1$}}
$F_i=min${$F_j-A_j+1$}$+A_i
(A_i-A_j+1+1>k)
对于这种情况，只需保留最大的F_k-A_k+1即可。
F_i=min${$F_j$}$+k (A_i-A_j+1+1<=k)
对于这种情况，j必定为最小的那个。
因此转移可以优化到O(1)。
时间
O(n)
代码就不发了