CF1372E
MoyunAllgorithm
·
·
题解
给出一种最为好写好想、实现细节最少的写法。
题意
给你一个 N \times M 的矩阵，其中每行被分隔成若干个区间。你需要在矩阵中填 1 或 0，一个区间只能有 1 个 1。现在你需要让每一列的 1 的数量的平方和最大。求出这个值。
分析
一个应该想到的性质：我们应该尽可能让 $1$ 在一列摞起来。这样，平方和更大。事实上，样例就是一个很好的例子。那我们的状态可以定义为：
$dp_{i,j}$ 代表在横坐标 $[i,j]$，纵坐标 $[1,N]$ 的子矩阵内，最大列平方和。
枚举 $k \in [i,j]$。因为我们要让 $1$ 集中来加大平方和，因此我们要求 **所有左右端点均在 $[l,r]$ 内且经过 $k$ 的区间，都把 $1$ 放在 $k$ 上。** 之后，答案就是
$$dp_{i,j}= dp_{i,k-1}+cov_{i,j,k}+dp_{k+1,j}$$
答案即可求出。容易发现，这里的时间复杂度是 $O(N^3)$ （我们认为 $N,M$ 相同）。
如何求出 $cov_{i,j,k}$？目前题解区有 $2$ 种解法：二维差分与前缀和、开 $l,r$ 数组存端点等方法。它们的时间复杂度分别是 $O(N^3)-O(N^3)$、$O(N^3)-O(N^4)$（破折号前是预处理复杂度，后面是 dp 复杂度）。
但是其实可以直接在输入时直接预处理。对于输入的区间 $[la,ra]$，枚举所有 $lb \in [1,la],rb \in [ra,M],k \in [la,ra]$。之后把 $cov_{lb,rb,k}$ 更新即可。对于单个区间，它实现了最劣 $O(N^3)$ 的预处理。一共有 $N^2$ 量级的区间，但因为所有 $k$ 之和一定 $=N^2$，所以复杂度是 $O(N^4)$ 而不是 $O(N^5)$。
这样实现了 $O(N^4)-O(N^3)$ 的解法，可以通过本题。
```cpp
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN=505,MOD=998244353;
int N,M;
LL cov[105][105][105];
LL dp[105][105];
int main()
{
scanf("%d %d",&N,&M);
for(int i=1;i<=N;i++)
{
int t;
scanf("%d",&t);
for(int j=1;j<=t;j++)
{
int la,ra;
scanf("%d %d",&la,&ra);
for(int lb=la;lb;lb--)
for(int rb=ra;rb<=M;rb++)
for(int k=la;k<=ra;k++)
cov[lb][rb][k]++;
}
}
for(int i=1;i<=M;i++) dp[i][i]=cov[i][i][i]*cov[i][i][i];
for(int i=1;i<=M;i++) dp[i][i-1]=0;
for(int len=2;len<=M;len++)
{
for(int l=1;l+len-1<=M;l++)
{
int r=l+len-1;
for(int i=l;i<=r;i++)
{
dp[l][r]=max(dp[l][r],cov[l][r][i]*cov[l][r][i]+dp[l][i-1]+dp[i+1][r]);
}
}
}
printf("%lld\n",dp[1][M]);
return 0;
}
```