自动搬运

查看原文

来自洛谷，原作者为

	Felis ありふれた一日が素敵な日になっていくほら

搬运于2025-08-24 22:10:32，当前版本为作者最后更新于2019-05-20 13:51:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

手残了，第一次的题解少打了一个等于麻烦管理员大大重新审核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]}就可以了