首页 > 代码库 > Codeforces 713C Sonya and Problem Wihtout a Legend（单调DP）
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; }
Codeforces 713C Sonya and Problem Wihtout a Legend（单调DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。