Codeforces 713C Sonya and Problem Wihtout a Legend（单调DP）
【题目链接】 http://codeforces.com/problemset/problem/713/C
【题目大意】
给出一个数列，请你经过调整使得其成为严格单调递增的数列，调整就是给某些位置加上或者减去某个数，调整的代价是加上或者减去的数的绝对值之和，请你输出最小代价。
【题解】
先考虑这样一个问题，如果是非严格单调递增该如何做，我们会发现每次调整，都是调整某个数字为原先数列中存在的数字，最后才是最优的，所以，我们设DP[i][j]表示前i个数字，最后一个数为原先数列排序后第j大的数字的最小代价，那么做一遍n2的DP就能够获得答案，现在题目中要求的是严格单调递增，那么就用到一种经典的处理方法，a[i]=a[i]-i，这样子就转化为非严格单调的问题了。
【代码】
#include <cstdio>
#include <algorithm>
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;
}
评论 (0)
