#P18112. Dynamic Adjustment
Dynamic Adjustment
Dynamic Adjustment
对整数数组 ,定义
$$f(a)=\min_{b_1\le\cdots\le b_m}\sum_{j=1}^{m}|a_j-b_j|,$$其中 可以是任意整数,不要求属于原数组。
给定数组 和位置排列 。对每个 ,把位置 按从小到大排序为 ,形成子序列 。求这 个子序列各自的 。
注意,子序列按原数组位置排列,不是按加入时间,也不是按数值排序。
输入格式
第一行整数 ,。
第二行 个整数 ,。
第三行 的一个排列 。
输出格式
输出 个整数,第 个是前 个位置加入后的最小修改代价。
样例1
5
5 4 3 2 1
1 2 3 4 5
0 1 2 4 6
样例2
3
3 2 1
1 3 2
0 2 2
样例2的子序列依次为 、、。后两者修改成常值数组都能达到代价2。