题目链接 https://codeforces.com/contest/1372/problem/E
题面 
文章图片
题意 给定一个 n ? m n*m n?m的矩形区域，然后有接下来给定每行划分的区域，每行 k k k个区域，区域由区间 [ L , R ] [L,R] [L,R]表示，你可以把区间赋值为 01 01 01串，但是只能每个区域一个 1 1 1，然后求每一列和的平方的和最大。
思路 【ACM|Codeforces Round #655 (Div. 2) E】不难知道要尽量使一列的 1 1 1更多，答案才尽可能大，考虑区间 d p dp dp， d p [ i ] [ j ] dp[i][j] dp[i][j]表示为：表示从i i i列到j j j列能够得到的最大值，枚举中间某列k k k，使这一列尽可能多地放1 1 1作为区间分界（根据每个区间的左右来进行判断），然后就是 O ( n 3 ) O(n^3) O(n3)的区间 d p dp dp加枚举的 O ( n ) O(n) O(n)，总的复杂度就是 O ( n 4 ) O(n^4) O(n4)。
参考代码
#include
using namespace std;
const int N = 1e2 + 10;
int n, m, dp[N][N], L[N][N], R[N][N];
int main() {
cin >> n >> m;
for (int i = 1;
i <= n;
i++) {
int k;
cin >> k;
while (k--) {
int l, r;
cin >> l >> r;
for (int j = l;
j <= r;
j++) {
L[i][j] = l;
R[i][j] = r;
}
}
}
for (int l = m;
l >= 1;
l--) {
for (int r = l;
r <= m;
r++) {
for (int k = l;
k <= r;
k++) {
int temp = 0;
for (int i = 1;
i <= n;
i++) {
if (L[i][k] >= l && R[i][k] <= r) {
temp++;
}
}
dp[l][r] = max(dp[l][r], dp[l][k - 1] + dp[k + 1][r] + temp * temp);
}
}
}
cout << dp[1][m] << endl;
return 0;
}
推荐阅读
- 数据结构和算法|LeetCode 的正确使用方式
- #|7.分布式事务管理
- #|算法设计与分析（Java实现）——贪心算法（集合覆盖案例）
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- #|阿尔法点亮LED灯(一）汇编语言
- #|Multimedia
- #|ARM裸机开发（汇编LED灯实验（I.MX6UL芯片））
- 基础课|使用深度优先搜索（DFS）、广度优先搜索（BFS）、A* 搜索算法求解 (n^2 -1) 数码难题，耗时与内存占用（时空复杂度）对比（附（(n^2 - 1) 数码问题控