題意：

N個(gè)數(shù)。a1...aN。

對(duì)于每個(gè)數(shù)而言，每一步只能加一或減一。

問(wèn)最少總共需要多少步使得新序列是非遞減序列。

N?(1?≤?N?≤?5000)

?

思路：

*一個(gè)還不知道怎么證明的結(jié)論（待證）：最后的新序列b1...bN中的每一個(gè)數(shù)bi，一定是原a1..aN序列中的某個(gè)數(shù)。

將a1..aN從小到大排列，得到c1...cN。

dp[i][j]：原序列前i個(gè)數(shù)經(jīng)過(guò)操作，第i個(gè)數(shù)不超過(guò)c[j]所花最少步數(shù)。

dp[i][j]=min( dp[i-1][j]+abs(a[i]-b[j]),dp[i][j-1] )

然后用滾動(dòng)數(shù)組。

?

代碼：

int const N=5005; int n; ll a[N],b[N]; ll dp[N];int main(){cin>>n;rep(i,1,n){scanf("%I64d",&a[i]);b[i]=a[i];}mem(dp,0);dp[0]=INF;sort(b+1,b+1+n);rep(i,1,n){ //前i個(gè)rep(j,1,n){ //最后一個(gè)高度不超過(guò)第b[j]個(gè)的高度dp[j]=min( dp[j]+abs(a[i]-b[j]),dp[j-1] );}}ll ans=INF;rep(i,1,n){ans=min(ans,dp[i]);}printf("%I64d\n",ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/fish7/p/4318136.html

總結(jié)

以上是生活随笔為你收集整理的cf13C Sequence（DP）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。