# CFR 571 B. Minimization ( DP )

Problem - B - Codeforces

2 ≤ n ≤ 3e5, 1 ≤ k ≤ min(5000, n - 1)
- 1e9 ≤ A[i] ≤ 1e9
TL: 2000 ms
ML: 256 MB

dp[ i ][ j ]：已創造 i 個 N / K 大小的群，以創造 j 個 N / K + 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;
}
```