http://codeforces.com/contest/713
题目大意：给你一个长度为n的数组，每次有+1和-1操作，在该操作下把该数组变成严格递增所需要的最小修改值是多少
思路：遇到这类题型，最普遍的方法就是把严格递增给变为递增就好了，所以我们对所有的a进行处理，a[i]-=i，然后再dp。
我们对dp进行如下的定义：定义dp[i][j]，dp[i][j]表示前i个数，1~i-1个数的val都<=b[j]，目前第i个数修改成b[j]（即第j大的数），所需要的最小花费dp[i][j] = min(dp[i][j - 1], dp[i - 1][j] + abs(a[i] - b[j]));
因此我们就进行转移就好了
//看看会不会爆int!数组会不会少了一维！
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha; printf("haha\n");
/*
我们定义，dp[i][j]表示前i个数，1~i-1个数的val都<=b[j]，
目前第i个数修改成b[j]（即第j大的数），所需要的最小花费
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j] + abs(a[i] - b[j]));
*/
const int maxn = + ;
LL dp[maxn][maxn];
LL a[maxn], b[maxn];
int n; int main(){
scanf("%d", &n);
for (int i = ; i <= n; i++){
scanf("%d", a + i);
a[i] -= i;
b[i] = a[i];
}
sort(b + , b + n + );
for (int i = ; i <= n; i++){
dp[i][] = dp[i - ][] + abs(a[i] - b[]);
for (int j = ; j <= n; j++){
dp[i][j] = min(dp[i][j - ], dp[i - ][j] + abs(a[i] - b[j]));
}
}
printf("%I64d\n", dp[n][n]);
return ;
}