[poj3666]Making the Grade(DP/左偏树)

时间:2023-03-09 02:15:10
[poj3666]Making the Grade(DP/左偏树)

题目大意:给你一个序列a[1....n],让你求一个序列b[1....n],满足 bi =a && bc,则最小的调整可以是把b变成c.

所以归纳可知上面结论成立。

dp[i][j] 表示考虑前i个元素,最后元素为序列中 第j小元素的最优解,a[]数组存原始数组,b[]是对a从小到大排序。

dp[i][j] = MIN(dp[i-1][k]) + abs(a[i]-b[j]), (0