Sonya and Problem Wihtout a Legend CF713C 题解

· · 题解

第一道紫题

题面翻译

给定一个有 n 个正整数的数组，一次操作中，可以把任意一个元素加一或减一。（元素可被减至负数或 0），求使得原序列严格递增的求最小操作次数。

样例

样例输入

7
2 1 5 11 5 9 11

样例输出

9

可将样例序列变为 2 3 5 6 7 9 11。

这道题和CF13C有异曲同工之妙。

只不过 CF13C 是非严格递增（序列之间的数可以相等），此题是严格递增（必须小于）。

先看这篇题解 。

我的题解（CF13C）

我们现在只需要想如何让数列成为严格递增。

我们可以让 a_i - i，即使a_i - i 与 a_{i-1} - (i-1) 相等，展开为

a_i=a_{i-1}-i+i+1 a_i=a_{i-1}+1

这样就是一个严格递增的数列了。

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N=50005;
int a[N];
int f[2][N];
int b[N];
int n,m;
signed main(){
    int  n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        b[i]=a[i]=a[i]-i;//只改了这里
    }
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++){
        f[1][0]=1e18;
        for(int j=1;j<=n;j++){
            f[1][j]=min(f[1][j-1],f[0][j]+abs(a[i]-b[j]));
        }
        for(int j=1;j<=n;j++) f[0][j]=f[1][j];

    }
    cout<<f[1][n];
    return 0;
}