本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-21 16:13:17

第一道紫题

题面翻译

给定一个有 $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;
}