题意：给你n个数字，每个数字可以加减任何数字，付出变化差值的代价，求最后整个序列是严格单调递增的最小的代价。

　　首先我们要将这个题目进行转化，因为严格单调下是无法用下面这个dp的方法的，因此我们转化成非严格的，对严格下而言，a[j]-a[i]>=j-i，那么得到a[i]-i<=a[j]-j。这样，我们令a'[i] = a[i] - i，就可以得到a'[i]<=a'[j]。这样我们就把问题转化成求这样一个非严格单调的序列了。

　　将整个序列排序后构成一个新的数组b[i]，用dp[i][j]来表示到第 i 个数字的时候，这个数字正好是b[j]或者比b[j]更小的最小代价。那么我们可以得到转移方程如下：dp[i][j]可以从dp[i][j-1]转化而来，因为b数组是单调的，所以既然 i 这个位置更小了，后面的肯定也满足单调，那么就可以直接转化了，或者说dp[i][j]可以从dp[i][k](1<=k<=j-1)中的最小值转化而来，另外dp[i][j]可以由dp[i-1][j]+abs(a[i]-b[j])转化过来，也就是说，前i-1个已经满足，那么第 i 个变成b[j]即可，当然这付出的代价是abs(a[i]-b[j])。这样我们就把dp过程写好了，复杂度是O(n^2)，我们还可以把b数组进行去重处理以优化。另外我们还可以用滚动数组来优化空间复杂度。

　　具体见代码：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N =  + ;

 ll dp[][N];

 ll a[N];

 vector<ll> V;

 int main()

 {

     memset(dp,,sizeof(dp));

     int n;

     cin >> n;

     for(int i=;i<=n;i++)

     {

         scanf("%I64d",a+i);

         a[i] -= i;

         V.push_back(a[i]);

     }

     sort(V.begin(),V.end());

     V.erase(unique(V.begin(),V.end()),V.end());

     int now = , pre = ;

     for(int i=;i<=n;i++)

     {

         now ^= , pre ^= ;

         dp[now][] = dp[pre][] + abs(a[i]-V[]);

         for(int j=;j<V.size();j++)

         {

             dp[now][j] = min(dp[now][j-],dp[pre][j]+abs(a[i]-V[j]));

         }

     }

     cout << dp[now][V.size()-] << endl;

     return ;

 }

　　另外poj3666也是类似的，那个题目的意思是，把序列变成非严格递增或递减，需要的最小代价。那么我们连转化都不需要了，只要再来一遍递减的就可以了（话说很多人的博客说这题的数据水，只要处理完递增的就可以了）。

　　再看类似的一题，hdu5256。现在不是求最小代价了，而是求最少需要变化几个元素使得满足严格递增。套路还是一样的，我们先装化成非严格的套路来。之后我们求出其最长不下降序列（就是把LIS的过程中换成upper_bound即可）的个数t，答案就是len-t。仔细琢磨一下的话还是觉得非常奥义的！