對於不嚴格單調的我們可以n^2DP,首先每個數一定在原數組中出現過,如果沒出現過不如減小到出現過的那個花費更小,效果相同
所以f[i][j]表示把i改到離散化后j的最小代價,每次維護前一狀態最小值mn再加上這次的值就是答案
圖像沒看懂:https://blog.csdn.net/lycheng1215/article/details/80089004
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=3009; const ll inf=1e18+5; int n,a[maxn],b[maxn]; ll f[maxn][maxn],mn[maxn]; inline ll min(ll a,ll b){return a<b?a:b;} inline ll abs(ll a){return a<0?-a:a;} 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+1+n); int bb=unique(b+1,b+1+n)-b-1; for(int i=1;i<=n;i++){ ll mn=inf; for(int j=1;j<=bb;j++){ mn=min(mn,f[i-1][j]); f[i][j]=abs(b[j]-a[i])+mn; } } ll ans=inf; for(int i=1;i<=bb;i++) ans=min(ans,f[n][i]); printf("%lld\n",ans); }