本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
\(\mathcal{Description}\)
Link.
给定一个 \(n \times m\) 的矩阵，每行被划分为若干段，你可以钦定每段中恰好一个位置为 \(1\)，其余位置为 \(0\)。设 \(c_i\) 为第 \(i\) 列 \(1\) 的个数，最大化 \(\sum_{i=1}^{m} c_i^2\)。
\(n,m\le100\)。
\(\mathcal{Solution}\)
区间 DP，不过状态设计比较巧妙：令 \(f(l,r)\) 表示确定在 \([l,r]\) 区间内的所有段的最大和。记 \(c_{l,r,k}\) 表示在区间 \([l,r]\) 内，包含了第 \(k\) 列的段的个数，转移：
\[ f(l,r)=\max_{k\in[l,r]}\{f(l,k-1)+f(k+1,r)+c_{l,r,k}^2\}
\]
复杂度 \(\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\n", f[1][m] );
return 0;
}
