Codeforces Round #655 (Div. 2) E

文章目录[x]
  1. 1:题目链接
  2. 2:题面
  3. 3:题意
  4. 4:思路
  5. 5:参考代码




E

题目链接

https://codeforces.com/contest/1372/problem/E

题面

在这里插入图片描述

题意

给定一个的矩形区域,然后有接下来给定每行划分的区域,每行个区域,区域由区间表示,你可以把区间赋值为串,但是只能每个区域一个,然后求每一列和的平方的和最大。

思路

不难知道要尽量使一列的更多,答案才尽可能大,考虑区间表示为:表示从 列到 列能够得到的最大值,枚举中间某列 ,使这一列尽可能多地放 作为区间分界(根据每个区间的左右来进行判断),然后就是的区间加枚举的,总的复杂度就是

参考代码

#include <bits/stdc++.h>
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;
}


点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像