ACM|Codeforces Round #655 (Div. 2) E

题目链接 https://codeforces.com/contest/1372/problem/E
题面 ACM|Codeforces Round #655 (Div. 2) 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; }

    推荐阅读