因为这个题：弱下定决心要好好做dp！因为代码跟poj 3666太像了！数学脑洞思维是真的需要啊


POJ 3666：求不升的DP

这个题是求升序的DP，那么有什么变化呢

不升的条件是：a【i】-a【j】>=0

升序的条件是：对任意的i，j：a【i】-a【j】>=i-j

看到什么了吗？移项有：a【i】-i>=a【j】-j

所以，把a数组变形一下，跟POJ3666就是一个题！


代码如下：

#include<bits/stdc++.h>
using namespace std;

#define LL __int64

const int maxn=3050;
const LL INF=0x3f3f3f3f3f3f3f3f;
int n,m;
LL a[maxn],b[maxn];
LL dp[maxn][maxn];

int main(){
    //freopen("input.txt","r",stdin);
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++){
            scanf("%I64d",&a[i]);
            a[i]=a[i]-i;
            b[i]=a[i];
        }
        sort(b+1,b+n+1);
        m=1;
        for(int i=2;i<=n;i++)
            if (b[i]!=b[i-1]) b[++m]=b[i];
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            LL Min=INF;
            for(int j=1;j<=m;j++){
                Min=min(Min,dp[i-1][j]);
                dp[i][j]=abs(b[j]-a[i])+Min;
            }
        }
        LL ans=INF;
        for(int i=1;i<=m;i++)
            ans=min(ans,dp[n][i]);
        printf("%I64d\n",ans);
    }
    return 0;
}