世界信息:CF13C. Sequence

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

世界信息:CF13C. Sequence

2023-01-04 20:58:57 来源：博客园

(资料图)

题目描述

$\qquad$给你一个序列$\large a$，要求你把它变成一个递增的序列，将目标序列与这个序列对应位置上所有数的差值和成为修改花费，求最小的修改花费。

解题思路

$\qquad$对于序列上的修改是一眼$DP$，具体是应该如何去$DP$

$\qquad\qquad$首先我们思考一下，可以得到一个重要性质，就是我们最小花费的目标序列，必定是由原先序列的数字构成的。

推导

$\qquad$因为我们可以将由原先序列的数字加减后成员不变构成的新序列看成是由原先的序列经过一系列的交换操作后得到的，而成员不同的新序列是由原先的序列经过一系列的交换然后再加减得到的，那么我们不做额外的加减操作，花费肯定是比额外的要小的，因此我们只需要从原序列上考虑就行了

$\qquad$所以我们就可以得到我们的$DP$：

状态表示

\[f[i][j]表示让前 i 个数保持升序，并且最大的数不大于原序列排行第 j 个数的最小花费\]

DP边界

\[f[0][i]=0，因为没有符合的一定没有花费。其他的都是正无穷\]

转移方程

我们可以将一个情况分成两类：$\qquad 1.$第$i$个数本来排名就在第$i$位，可以安插$$f[i][j]=f[i][j-1]$$$\qquad 2.$第$i$个数和目标序列第$i$位不同，需要改，所以$$f[i]][j] = f[i - 1][j] + abs(c[j]-a[i])$$以上两种取$min$即可

代码

#include #include #include #define int long longusing namespace std;const int N = 5e4 + 10;int f[2][N], n, a[N], c[N];signed main() {scanf("%lld", &n);for (int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]), c[i] = a[i];sort(c + 1, c + 1 + n);memset(f, 0x3f, sizeof f);for (int i = 1; i <= n; i ++ ) f[0][i] = 0;for (int i = 1; i <= n; i ++) {for (int j = 1; j <= n; j ++ ) f[1][j] = min(f[1][j - 1], f[0][j] + abs(c[j] - a[i]));swap(f[0], f[1]);}int res = 1e18;for (int i = 1; i <= n; i ++ )  res = min(res, f[0][i]);printf("%lld\n", res);return 0;}

关键词：转移方程因为我们该如何去