CF2053F Earnest Matrix Complement 题解
Gold14526
·
·
题解
### 题意
给定一个 $n\times m$ 的矩阵 $A$，每个数在 $[1,k]$ 间，其中有一些数待填。
定义该矩阵的权值为：
$$\sum_x\sum_{i=1}^{n-1}cnt_{x,i}cnt_{x,i+1}$$
其中 $cnt_{x,i}$ 表示 $x$ 在第 $i$ 行出现的次数。
求填完数后该矩阵权值最大值。
$1\le n,m\le2\times10^5,1\le k\le n\times m\le6\times10^5$。
### 做法
首先发现每行只会填一种数，否则替换成上下两行出现次数总和最多的数一定不劣。
先把已知的数的贡献算出来，然后只需要考虑填的数造成的影响。
不难得到朴素 dp 方式：
设 $f_{i,j}$ 表示考虑前 $i$ 行，第 $i$ 行填的数是 $j$ 的方案数。
不难发现 $f_{i,j}$ 只会从 $f_{i-1,j}$ 或 $f_{i-1}$ 中的最大值转移过来，设这个最大值是 $mx_{i-1}$，第 $i$ 行的待填数有 $emp_i$ 个，那么可以得到转移式：
$$f_{i,j}=\max(f_{i-1,j}+emp_iemp_{i-1},mx_{i-1})+emp_i(cnt_{i-1,j}+cnt_{i+1,j})$$
（这里的 $cnt_{i,j}$ 表示在输入给出的已知数中，$j$ 在第 $i$ 行出现的次数）
式子可能有点长，我们拆成两步看：
$$f_{i,j}=\max(f_{i-1,j}+emp_iemp_{i-1},mx_{i-1})$$
$$f_{i,j}:=f_{i,j}+emp_i(cnt_{i-1,j}+cnt_{i+1,j})$$
发现第一步转移对所有的 $j$ 都一样，可以直接全局加，全局取 $\max$。
第二步总转移次数是上下两行出现数字个数之和，也就是一共 $O(nm)$ 次单点加。
所以只要维护一个能支持全局加，全局取 $\max$，单点加，求全局 $\max$ 的东西就可以了，可以用线段树之类的东西实现，不过打个全局标记就可以了，这样每次就是 $O(1)$ 的，具体可以看代码。
### 代码
一个能支持全局加，全局取 $\max$，单点加，求全局 $\max$ 的东西：
```cpp
namespace A{
ll addtag,maxtag;
ll a[600001];
ll mx;
void clear()
{
for(int i=1;i<=k;++i)a[i]=0;
addtag=maxtag=mx=0;
}
void alladd(cll x)
{
addtag+=x;
maxtag+=x;
}
void allmax(cll x)
{
maxtag=max(maxtag,x);
}
void add(cint x,cll y)
{
a[x]=max(a[x],maxtag-addtag);
a[x]+=y;
mx=max(mx,a[x]);
}
ll ask()
{
return max(maxtag,mx+addtag);
}
}
```
dp 部分：
```cpp
for(int i=1;i<=n;++i)
{
cll lstans=A::ask();
A::alladd(1ll*emp[i]*emp[i-1]);
A::allmax(lstans);
for(int x:a[i-1])
{
if(x==-1)continue;
A::add(x,emp[i]);
}
if(i<n)
{
for(int x:a[i+1])
{
if(x==-1)continue;
A::add(x,emp[i]);
}
}
}
```
提交记录：
[submission](https://codeforces.com/contest/2053/submission/298883196)