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

題意：
給一個矩陣，表示每對人之間的憎恨值。現在要把人划分為 K 群，每群必須都是連續編號的人。一個群的憎恨值貢獻是所有編號的有序對的憎恨值總和。求最少憎恨值總和。

資料規模：
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 ( 參照轉移式 )
會有 opt[ i ][ j - 1 ] ≤ opt[ i ][ j ] ≤ opt[ i ][ j + 1 ], for all j
那麼只要分治，就能不斷壓縮更新時的搜索範圍，複雜度便是好的。
這題的瓶頸反而在輸入，連 scanf 也會 TLE。
因為一行最多會有 4000 個整數，所以用 getline()，一下就壓到 1152 ms。

時間 / 空間複雜度：
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;
}