专栏文章

题解：CF2053F Earnest Matrix Complement

IIvanZhang2009
CF2053F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqmi1fm
此快照首次捕获于
2025/12/04 07:13
3 个月前
此快照最后确认于
2025/12/04 07:13
3 个月前
查看原文
本题最关键的结论是：每一行只会填一种数。考虑用调整法证明，设一行填了两种数，则考虑这两种数在上下两行中的出现次数，如果不一样则显然填一种可以更优；若一样则填一种等价。
于是可以设计最简单的 dp：fi,jf_{i,j} 表示第 ii 行的 −1-1 全部填成 jj 的最大贡献。此时把贡献如此拆：两行中都不是 −1-1 的提前算出来；设上下两行中出现 jj 的次数为 cojco_j，上一行和本行的问号个数为 c0,c1c_0,c_1，则在 fi,jf_{i,j} 转移时加入 coj×c1co_j\times c_1；两行都是 −1-1 的贡献在转移中记为 c0c1c_0c_1。转移为 fi,j=cojc1+max⁡fi−1,k+[j=k]c0c1f_{i,j}=co_jc_1+\max f_{i-1,k}+[j=k]c_0c_1。注意到可以提前处理出 max⁡fi−1,k\max f_{i-1,k} 做到 O(1)O(1) 转移，时间复杂度 O(nk)O(nk)，无法通过。
我们考虑维护整个 dp 数组的变化。注意到这玩意可以变成三个可以接受的操作：
  • 全局加 c0c1c_0c_1。
  • 全局对 max⁡fi−1,k\max f_{i-1,k} 取 max⁡\max。
  • 对于所有有值的 cojco_j，单点加 cojc1co_jc_1。
按顺序做这三个操作，并实时维护 max⁡\max 即可。注意到大部分操作是全局操作，我们设计一个标记 (a1,…n,x,y)(a_{1,\dots n},x,y)，表示此时 fj=max⁡(aj+x,y)f_{j}=\max(a_j+x,y)。考虑三种操作，全局加 zz 即让 x,yx,y 都加 zz；全局对 zz 取 max⁡\max 即令 yy 对 zz 取 max⁡\max。单点加的时候只需要求出当前的单点值，设做单点加后值为 zz，注意到一定有 z>yz>y，我们直接令 aj←z−xa_j\leftarrow z-x 即可。max⁡\max 与这三种操作同时维护即可。时间复杂度 O(nm+k)O(nm+k)。
CPP
#include<bits/stdc++.h>
using namespace std;
#define int         long long
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
#define over(x)     {cout<<(x)<<endl;return;}
int n,m,t;
int f[4000005],X,Y,g[1000005],c[1000005];
void Main() {
	cin>>n>>m>>t;
	vector<vector<int>>a(n, vector<int>(m));
	vector<int>cnt(n);
	REP(i,0,n){
		cnt[i]=0;
		vector<int>b;
		REP(j,0,m){
			int x;cin>>x;
			if(x>0)b.pb(x-1);
			else ++cnt[i];
		}
		reverse(all(b));REP(j,0,cnt[i])b.pb(-1);
		reverse(all(b));a[i]=b;
	}
	if(n==1)over(0)
	REP(i,0,t)f[i]=0;
	int ans=0;
	REP(i,0,n-1){
		REP(j,cnt[i],m)++f[a[i][j]];
		REP(j,cnt[i+1],m)ans+=f[a[i+1][j]];
		REP(j,cnt[i],m)--f[a[i][j]];
	}
	REP(j,cnt[1],m)f[a[1][j]]+=cnt[0];
	X=Y=0;int mx=0;
	REP(i,0,t)mx=max(mx,f[i]);
	REP(i,1,n){
        vector<int>T;
        REP(j,cnt[i-1],m)T.pb(a[i-1][j]);
        if(i<n-1)REP(j,cnt[i+1],m)T.pb(a[i+1][j]);
        for(auto j:T)c[j]=0;
        for(auto j:T)++c[j];
        int co=cnt[i]*cnt[i-1];
        X+=co;Y=max(Y+co,mx);mx+=co;
        for(auto j:T)if(c[j]){
            f[j]=max(X+f[j],Y)+c[j]*cnt[i];
            mx=max(mx,f[j]);
            f[j]-=X;c[j]=0;
        }
	}
	mx=0;
	REP(j,0,t)mx=max(mx,max(f[j]+X,Y));
	over(mx+ans)
}
void TC() {
    int tc=1;
    cin>>tc;
	while(tc--){
		Main();
		cout.flush();
	}
}
signed main() {
	return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0;
}
/*
1. CLEAR the arrays (ESPECIALLY multitests)
2. DELETE useless output
 */

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...