CFR 360 B. Levko and Array ( DP, Binary Search )
題意:
給一個數列,可以更改至多 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; }