cfCodeforces Round #371 714E - Sonya and Problem Wihtout a Legend - dp +lis

http://codeforces.com/problemset/problem/714/E

 

题意：给一个序列，可以给每一个数假减一个数，代价为他们改变的数的绝对值，那么要求用最小代价把序列变成严格递增的

有一个非严格递增的版本 为poj 3666： http://blog.csdn.net/viphong/article/details/52535780

而本题的严格如何转化非严格，直接加一行代码，a[i]-=i；

原理

推导过程大致如下：a[i] < a[i+1] ——> a[i] <= a[i+1]-1 ——> a[i]-i <= a[i+1]-(i+1)——> b[i]<=b[i+1]

L参考： #include <cstdio> #include <cmath> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <map> #include <set> #include <vector> #include <iostream> using namespace std; const int N=3005; int n; int a[N],b[N]; long long dp[N][N]; void solve() { 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("%lld\n",ans); } 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); solve(); return 0; }