题目链接 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) 数码问题控