CF2053F Earnest Matrix Complement 题解

\rm Problem:

Earnest Matrix Complement

题意

给定一个

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

CF2053F Earnest Matrix Complement 题解

文章操作

题意

做法

代码

相关推荐

评论

CF2053F Earnest Matrix Complement 题解