https://codeforces.com/problemset/problem/714/E
跟poj3666差不多
https://blog.csdn.net/liufengwei1/article/details/102844609
不过这里是要求B数列是严格上升子序列
我们可以构造a[i]=a[i]-i,这样就保证了A序列至少相差了1，那么最后只要求对于新的A序列的构造不严格上升子序列的答案就可以了
#include<bits/stdc++.h> #define maxl 3010 using namespace std; int n,m; int a[maxl],b[maxl]; long long ans; long long f[maxl][maxl]; inline void prework() { 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+1+n); m=unique(b+1,b+1+n)-b-1; } inline void mainwork() { long long tmp; for(int i=1;i<=n;i++) { tmp=1ll<<62; for(int j=1;j<=m;j++) { tmp=min(tmp,f[i-1][j]); f[i][j]=tmp+abs(a[i]-b[j]); } } ans=1ll<<62; for(int j=1;j<=m;j++) ans=min(ans,f[n][j]); } inline void print() { printf("%lld",ans); } int main() { prework(); mainwork(); print(); return 0; }
