题意：一串数字，要求变成严格的上升子序列的最小花费，花费为abs(a-temp)
题解：做这题之前，可以先去做做hdu5256
考虑两个位置i,j(i<j)的数a[i]和a[j]，要是严格上升，那么肯定有a[j] - a[i] >= j - i ，也就是说a[j] - j >= a[i] - i
那么考虑新的数列a[i] - i，只要保证这个数列是上升的就可以(可以存在相等)
首先把a[i]都变成a[i] - i，然后对其排序，新的序列记为b[i]
dp[i][j] 表示，处理到第i位时，如果以b[j]为基准构造序列的最小花费
dp[i][j] = min(dp[i][j-1]，dp[i-1][j] + abs(a[i]-b[j]))
考虑到当前的dp[i][j]，可以从dp[i][j-1]转换而来，因为b[j-1] < b[j]，如果前半部分b[j-1]为基准构成的序列，而后半部分是以b[j]构成的序列，那么肯定是没有影响的，因为a[i]位置以b[j-1]为基准构成的数肯定小于等于以b[j]为基准构成的数。或者是从dp[i-1][j]转换而来，加上abs(a[i] - b[j])即可
想了好久。。。
int a[3010]; int b[3010]; LL dp[3010][3010]; int main(){ int n; while(cin>>n){ memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); a[i]-=i; b[i]=a[i]; } sort(b+1,b+n+1); for(int i=1;i<=n;i++){ dp[i][1]=dp[i-1][1]+abs(a[i]-b[1]); for(int j=2;j<=n;j++){ dp[i][j]=min(dp[i][j-1],dp[i-1][j]+abs(a[i]-b[j])); } } cout<<dp[n][n]<<endl; } return 0; }
