题解：CF2053F Earnest Matrix Complement

· · 题解

本题最关键的结论是：每一行只会填一种数。考虑用调整法证明，设一行填了两种数，则考虑这两种数在上下两行中的出现次数，如果不一样则显然填一种可以更优；若一样则填一种等价。

于是可以设计最简单的 dp：f_{i,j} 表示第 i 行的 -1 全部填成 j 的最大贡献。此时把贡献如此拆：两行中都不是 -1 的提前算出来；设上下两行中出现 j 的次数为 co_j，上一行和本行的问号个数为 c_0,c_1，则在 f_{i,j} 转移时加入 co_j\times c_1；两行都是 -1 的贡献在转移中记为 c_0c_1。转移为 f_{i,j}=co_jc_1+\max f_{i-1,k}+[j=k]c_0c_1。注意到可以提前处理出 \max f_{i-1,k} 做到 O(1) 转移，时间复杂度 O(nk)，无法通过。

我们考虑维护整个 dp 数组的变化。注意到这玩意可以变成三个可以接受的操作：

按顺序做这三个操作，并实时维护 \max 即可。注意到大部分操作是全局操作，我们设计一个标记 (a_{1,\dots n},x,y)，表示此时 f_{j}=\max(a_j+x,y)。考虑三种操作，全局加 z 即让 x,y 都加 z；全局对 z 取 \max 即令 y 对 z 取 \max。单点加的时候只需要求出当前的单点值，设做单点加后值为 z，注意到一定有 z>y，我们直接令 a_j\leftarrow z-x 即可。\max 与这三种操作同时维护即可。时间复杂度 O(nm+k)。

#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
 */