题意：给一个序列，可以进行若干次操作，每次操作选择一个数让它+1或-1，问最少要几次操作使得序列变为严格单调递增序列。
题解：首先考虑非严格递增序列，则每个数字最终变成的数字一定是该数组中的某个数。那么O(n^2)复杂度dp一下即可。
dp[i][j]表示第i个数变成第j小的数，dp[i][j] = min (dp[i-1][1 ... j])+abs(a[i]-b[j]).
那么对于严格递增序列，将a[i]变成a[i]-i后，再照非严格递增序列跑一遍dp即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[][];
int a[], b[];
int main(){
int n;
cin >> n;
for(int i = ; i <= n; i++) {
cin >> a[i];
a[i] -= i;
b[i] = a[i];
}
sort(b+, b+n+);
int tot = unique(b+, b+n+)-b;
memset(dp, 0x3f, sizeof(dp));
for(int j = ; j < tot; j++) dp[][j] = ;
for(int i = ; i <= n; i++)
for(int j = ; j < tot; j++){
dp[i][j] = abs(a[i]-b[j])+dp[i-][j];
dp[i][j] = min(dp[i][j], dp[i][j-]);
}
printf("%lld\n", dp[n][tot-]);
return ;
}
更优秀的复杂度是O(nlogn)的解法。同样需要转为非严格递增。
int n;
priority_queue<long long> q; int main() {
scanf("%d",&n);
long long ans = ;
for(int i = ;i < n;i++) {
long long x;
scanf("%lld",&x);
x -= i;
q.push(x);
if(q.top() > x) {
ans += q.top()-x;
q.pop();
q.push(x);
}
}
printf("%lld\n",ans);
return ;
}