Link.

  给定一个 (n imes m) 的矩阵，每行被划分为若干段，你可以钦定每段中恰好一个位置为 (1)，其余位置为 (0)。设 (c_i) 为第 (i) 列 (1) 的个数，最大化 (sum_{i=1}^{m} c_i^2)。

  (n,mle100)。

(mathcal{Solution})

  区间 DP，不过状态设计比较巧妙：令 (f(l,r)) 表示确定在 ([l,r]) 区间内的所有段的最大和。记 (c_{l,r,k}) 表示在区间 ([l,r]) 内，包含了第 (k) 列的段的个数，转移：

  复杂度 (mathcal O(n^4))（求转移时在线求 (c_{l,r,k})）。

(mathcal{Code})

/* Clearink */

#include <cstdio>

const int MAXN = 100;
int n, m, f[MAXN + 5][MAXN + 5], L[MAXN + 5][MAXN + 5], R[MAXN + 5][MAXN + 5];

inline void chkmax ( int& a, const int b ) { a < b ? a = b : 0; }

int main () {
	scanf ( "%d %d", &n, &m );
	for ( int i = 1, k; i <= n; ++ i ) {
		scanf ( "%d", &k );
		for ( int j = 1, l = 1, r; j <= k; ++ j, l = r + 1 ) {
			scanf ( "%*d %d", &r );
			for ( int h = l; h <= r; ++ h ) L[h][i] = l, R[h][i] = r;
		}
	}
	for ( int len = 1; len <= m; ++ len ) {
		for ( int l = 1, r; ( r = l + len - 1 ) <= m; ++ l ) {
			int& cur = f[l][r] = -1;
			for ( int k = l; k <= r; ++ k ) {
				int c = 0;
				for ( int h = 1; h <= n; ++ h ) c += l <= L[k][h] && R[k][h] <= r;
				chkmax ( cur, f[l][k - 1] + f[k + 1][r] + c * c );
			}
		}
	}
	printf ( "%d
", f[1][m] );
	return 0;
}