题解 P5414 【[YNOI2019]排序】

· · 题解

手残了，第一次的题解少打了一个等于麻烦管理员大大重新审核QwQ

这道题就是移动几个数字使得数列单调上升，每次移动可以移动到任意位置，花费就是移动数字的大小。

看到这个题之后，我们可以得到 得不到的洗洗睡吧 ：最优解不可能把同一个数字移动2次及以上。既然我们可以一次把它移到正确的位置上，那么这个数字就可以理解为直接被移走了。

那么问题就变成了：删除几个数字，使得数列单调递增，所求的是移走数字的最小和。 使得删除的和最小，就意味着留下的和最大。

那么问题就变成了：保留几个单调递增的数字，使得和最大。

        for(int i=0;i<n;i++){
            for(int j=~0;j<i;j++)
            if(a[j]<=a[i])
                b[i]=max(b[i],b[j]);
            b[i]+=a[i];
        }

最后把数列每一个数的和减去Max{b[i]}就可以了