0w1

CFR 360 B. Levko and Array ( DP, Binary Search )

Problem - B - Codeforces

題意:
給一個數列,可以更改至多 K 個數,使成為任意數,求更改後最小的相鄰值絕對差。

資料規模:
The first line contains two integers n and k (1 ≤ k ≤ n ≤ 2000). The second line contains space-separated integers a1, a2, ... , an ( - 1e9 ≤ ai ≤ 1e9).
TL: 2000 ms
ML: 256 MB

解法:
考慮二分搜答案。若要判斷是否可以在最大相鄰絕對差 x 以內,那麼考慮 dp:
dp[ i ]:使 [ 0, i ] 合法,但 i 不修改的前提下,最小更改數量。
轉移 O( N ),枚舉下一個第一個不修改的下標 j,若將 [ i + 1, j ) 都適當的改,那麼 A[ i ] 和 A[ j ] 的絕對差允許在 x * ( j - i ) 內。
注意,這個狀態式無法表達有修改 A[ 0 ] 的情況,解決的方法之一是先訂上限: dp[ i ] = i。

時間 / 空間複雜度:
O( N lg A )

int N, K;
vi A;

void init(){
  cin >> N >> K;
  A = vi( N );
  for( int i = 0; i < N; ++i ){
    cin >> A[ i ];
  }
}

int ok( int x ){
  vi dp( N + 1 );
  for( int i = 0; i <= N; ++i ){
    dp[ i ] = i;
  }
  for( int i = 0; i < N; ++i ){
    for( int j = i + 1; j <= N; ++j ){
      if( j == N or abs( A[ j ] - A[ i ] ) <= 1LL * x * ( j - i ) ){
        upmin( dp[ j ], dp[ i ] + j - i - 1 );
      }
    }
  }
  return min( dp[ N - 1 ], dp[ N ] ) <= K;
}

void solve(){
  int ans = -1;
  for( int lb = 0, rb = ( int ) 2e9; lb <= rb; ){
    int mid = lb + ( rb - lb ) / 2;
    if( ok( mid ) ){
      ans = mid;
      rb = mid - 1;
    } else{
      lb = mid + 1;
    }
  }
  cout << ans << endl;
}