CFR 13 C. Sequence ( DP )

Problem - 13C - Codeforces

完全就是同一個題
只是這題要滾動才不會 MLE，然後詢問的是非遞減，所以不需要用到減下標的技巧。

題意：
給一個陣列 A，可以任意讓值 +1 或 -1 任意多次，問最少要幾次才能將 A 變成非遞減數列。

資料規模：
MAXA ≤ 1e9
N ≤ 5000
TL: 1000 ms
ML: 64 MB

解法：
考慮前面的元素都是非嚴格遞增的。這時候突然有一個違反這個條件的元素在尾端出現。那麼將它和它左邊的元素合併成一個集合，而這集合裡的所有值都是即合裡的數字的中位數一定是最優的。若集合元素為偶數，那麼無論是取中間靠左的那個，還是中間靠右的那個，花費不會有變化，而且都一定是最優的。可以這樣一直往左合併直到合法，再繼續原本的程序，這是上面的連結的作法 ( O( N lg^2 N ) )。這裏提供一個比較簡單的 DP，透過剛才的發現可以知道，修改後的值限定為原始數列的其中一個值後，一定不會丟失最優解。因此可以考慮動態規劃：
dp[ i ][ j ] : 已完成原數列前 i 項的修改且已合法，而且修改後的最後一項是 A 數列中第 j 小的元素。

最後，因為記憶體限制，所以第一維要改成滾動。

時間 / 空間複雜度：
O( N^2 ) / O( N )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5000;

int N;
int A[ MAXN ];
int ord[ MAXN ];
long long dp[ 2 ][ MAXN ];

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < N; ++i ){
    cin >> A[ i ];
    ord[ i ] = i;
  }
  sort( ord, ord + N, [ & ]( int i, int j ){ return A[ i ] < A[ j ]; } );
  for( int i = 0; i < N; ++i ){
    long long best = 1LL << 50;
    for( int j = 0; j < N; ++j ){
      best = min( best, dp[ i & 1 ][ j ] );
      dp[ ~i & 1 ][ j ] = best + abs( A[ i ] - A[ ord[ j ] ] );
    }
  }
  long long ans = 1LL << 50;
  for( int i = 0; i < N; ++i ){
    ans = min( ans, dp[ N & 1 ][ i ] );
  }
  cout << ans << endl;
  return 0;
}