【题目链接】 

 

【题目大意】

　　给出一个数列，请你经过调整使得其成为严格单调递增的数列，调整就是给某些位置加上或者减去某个数，调整的代价是加上或者减去的数的绝对值之和，请你输出最小代价。

 

【题解】

　　先考虑这样一个问题，如果是非严格单调递增该如何做，我们会发现每次调整，都是调整某个数字为原先数列中存在的数字，最后才是最优的，所以，我们设DP[i][j]表示前i个数字，最后一个数为原先数列排序后第j大的数字的最小代价，那么做一遍n²的DP就能够获得答案，现在题目中要求的是严格单调递增，那么就用到一种经典的处理方法，a[i]=a[i]-i，这样子就转化为非严格单调的问题了。

 

【代码】

#include 
     
       #include 
      
         using namespace std;  const int N=3010;  int n,a[N],b[N];  long long dp[N][N];  int main(){      scanf("%d",&n);      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++){          long long mn=dp[i-1][1];          for(int j=1;j<=n;j++){              mn=min(mn,dp[i-1][j]);              dp[i][j]=abs(a[i]-b[j])+mn;          }      }long long ans=dp[n][1];      for(int i=1;i<=n;i++)ans=min(ans,dp[n][i]);      printf("%I64d\n",ans);     return 0;  }