# CFR 321 E. Ciel and Gondolas ( DP, Monotonic, Divide and Conquer )

Problem - E - Codeforces

The first line contains two integers n and k (1 ≤ n ≤ 4000 and 1 ≤ k ≤ min(n, 800)) — the number of people in the queue and the number of gondolas. Each of the following n lines contains n integers — matrix u, (0 ≤ uij ≤ 9, uij = uji and uii = 0).
TL: 4000 ms

dp[ i ][ j ] : 已將前面的人劃分成 i 群，i 群一共有 j 個人，此時最小憎恨值總和。
dp[ i ][ j ] = min{ dp[ i - 1 ][ x ] + cost[ x ][ j - 1 ], 0 ≤ x < j }
cost[ i ][ j ] : [ i, j ] 的人組成的群的憎恨值。這個用二維前綴和搞一下就出來了。

opt[ i ][ j ] : 使 dp[ i ][ j ] 有最小值的最小 x ( 參照轉移式 )

O( K * N lg N ) / O( K * N )

```#include <bits/stdc++.h>
using namespace std;

template< class T1, class T2 >
int upmin( T1 &x, T2 v ){
if( x <= v ) return 0;
x = v; return 1;
}

const int INF = 0x3f3f3f3f;

const int MAXN = 4000;
const int MAXK = 800;

int N, K;
int G[ MAXN ][ MAXN ];
int pfx[ MAXN + 1 ][ MAXN + 1 ];
int cost[ MAXN ][ MAXN ];
int dp[ MAXK + 1 ][ MAXN + 1 ];
int opt[ MAXK + 1 ][ MAXN + 1 ];

void dfs( int n, int lb, int rb, int optL, int optR ){
if( rb < lb ) return;
int mid = lb + rb >> 1;
for( int i = optL; i <= min( mid - 1, optR ); ++i ){
if( upmin( dp[ n ][ mid ], dp[ n - 1 ][ i ] + cost[ i ][ mid - 1 ] ) ){
opt[ n ][ mid ] = i;
}
}
if( lb == rb ) return;
dfs( n, lb, mid - 1, optL, opt[ n ][ mid ] );
dfs( n, mid + 1, rb, opt[ n ][ mid ], optR );
}

signed main(){
ios::sync_with_stdio( 0 );
cin >> N >> K;
{ string buff; getline( cin, buff ); }
for( int i = 0; i < N; ++i ){
string buff; getline( cin, buff );
for( int j = 0; j < N; ++j ){
G[ i ][ j ] = buff[ j * 2 ] - '0';
}
}
for( int i = 1; i <= N; ++i ){
for( int j = 1; j <= N; ++j ){
pfx[ i ][ j ] = G[ i - 1 ][ j - 1 ] + pfx[ i ][ j - 1 ] + pfx[ i - 1 ][ j ] - pfx[ i - 1 ][ j - 1 ];
}
}
for( int i = 0; i < N; ++i ){
for( int j = i + 1; j < N; ++j ){
cost[ i ][ j ] = pfx[ j + 1 ][ j + 1 ] - pfx[ j + 1 ][ i ] - pfx[ i ][ j + 1 ] + pfx[ i ][ i ] >> 1;
}
}
memset( dp, INF, sizeof( dp ) );
opt[ 0 ][ 0 ] = dp[ 0 ][ 0 ] = 0;
for( int i = 1; i <= K; ++i ){
dfs( i, 1, N, 0, N - 1 );
}
cout << dp[ K ][ N ] << endl;
return 0;
}
```