题意：给一个序列，可以进行若干次操作，每次操作选择一个数让它+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即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 ll dp[3333][3333]; 5 int a[3333], b[3333]; 6 int main(){ 7 int n; 8 cin >> n; 9 for(int i = 1; i <= n; i++) { 10 cin >> a[i]; 11 a[i] -= i; 12 b[i] = a[i]; 13 } 14 sort(b+1, b+n+1); 15 int tot = unique(b+1, b+n+1)-b; 16 memset(dp, 0x3f, sizeof(dp)); 17 for(int j = 0; j < tot; j++) dp[0][j] = 0; 18 for(int i = 1; i <= n; i++) 19 for(int j = 1; j < tot; j++){ 20 dp[i][j] = abs(a[i]-b[j])+dp[i-1][j]; 21 dp[i][j] = min(dp[i][j], dp[i][j-1]); 22 } 23 printf("%lld ", dp[n][tot-1]); 24 return 0; 25 }
更优秀的复杂度是O(nlogn)的解法。同样需要转为非严格递增。
1 int n; 2 priority_queue<long long> q; 3 4 int main() { 5 scanf("%d",&n); 6 long long ans = 0; 7 for(int i = 0;i < n;i++) { 8 long long x; 9 scanf("%lld",&x); 10 x -= i; 11 q.push(x); 12 if(q.top() > x) { 13 ans += q.top()-x; 14 q.pop(); 15 q.push(x); 16 } 17 } 18 printf("%lld ",ans); 19 return 0; 20 }