0w1

CFR 571 B. Minimization ( DP )

Problem - B - Codeforces

題意:
給一個 n 個整數組成的數列,和一個數字 k。
f:id:h0rnet:20170114233133p:plain
任意排列數字,使得以上式子最小。

資料規模:
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;
}