CFR 571 B. Minimization ( DP )
題意:
給一個 n 個整數組成的數列,和一個數字 k。
任意排列數字,使得以上式子最小。
資料規模:
2 ≤ n ≤ 3e5, 1 ≤ k ≤ min(5000, n - 1)
- 1e9 ≤ A[i] ≤ 1e9
TL: 2000 ms
ML: 256 MB
解法:
注意到下標對 K 取模的數字們是一群的,而不同群的數字完全不會相互影響。假設一個群裡的數字都決定好了,那麼顯然排序後一定是最小的,而且此時該群的貢獻為最大值和最小值的差。接著考慮兩個群,最佳情況時顯然其中一個群的最大值一定不大於另一個群的最小值。群的大小,也只有兩種,N / K 和 N / K + 1。有幾個小群和大群可以用 N 和 K 直接導出,因此問題轉換為對排序過的原數列動態規劃。
dp[ i ][ j ]:已創造 i 個 N / K 大小的群,以創造 j 個 N / K + 1 大小的群,此時的最小總貢獻。
只要 i 和 j 確定,就能確定下標,而轉移只有兩種,到底也只是求差而已。狀態數 O( K ^ 2 ),轉移 O( 1 )。
時間 / 空間複雜度:
O( N + K ^ 2 )
int N, K; vi A; void init(){ cin >> N >> K; A = vi( N ); for( int i = 0; i < N; ++i ){ cin >> A[ i ]; } } vvl dp; void solve(){ sort( A.begin(), A.end() ); int small_sz = N / K; int large_cnt = N % K; int small_cnt = K - large_cnt; assert( small_sz * small_cnt + ( small_sz + 1 ) * large_cnt == N ); dp = vvl( small_cnt + 1, vl( large_cnt + 1, 1LL << 62 ) ); dp[ 0 ][ 0 ] = 0; for( int i = 0; i <= small_cnt; ++i ){ for( int j = 0; j <= large_cnt; ++j ){ int st = i * small_sz + j * ( small_sz + 1 ); if( i + 1 <= small_cnt ){ upmin( dp[ i + 1 ][ j ], dp[ i ][ j ] + abs( A[ st + small_sz - 1 ] - A[ st ] ) ); } if( j + 1 <= large_cnt ){ upmin( dp[ i ][ j + 1 ], dp[ i ][ j ] + abs( A[ st + small_sz ] - A[ st ] ) ); } } } cout << dp[ small_cnt ][ large_cnt ] << endl; }