我也不知道显不显然，有一个重要性质是：一定存在一种最优方案，使得每一行的 \(-1\) 填的都是同一个数。
证明的话直接调整即可，假设现在我们有一个最优方案，并且第 \(i\) 行填着不同的数，我们将每一种颜色 \(u\)，按 \(c_{u,i-1} + c_{u,i+1}\) 排个序，意思就是每多一个颜色 \(u\) 都会加上面的贡献，将其他颜色都调整为一个 \(c_{u,i-1} + c_{u,i+1}\) 最大的颜色，答案一定不会变小。
这样就好办了。设 \(f_{i,j}\) 为第 \(i\) 行中所有空位填的都是颜色 \(j\) 的最大权值。直接列出转移方程：
设 \(a_i\) 为第 \(i\) 行中 \(-1\) 的数量，\(b_{i,j}\) 为第 \(i\) 行中颜色 \(j\) 的数量。
\[f_{i,j} = \max_{c=1}^{k}(f_{i-1,c} + b_{i,c} \times a_{i-1} + a_i \times a_{i-1}[j = c]) + b_{i-1,j} \times a_i \]简单研究一下这个式子，发现其中只有 \(O(m)\) 次单点加，全局加和全局取 \(\max\)。然后维护全局 \(\max\)。此时我的大脑已经停转了，直接上线段树维护即可，时间复杂度 \(O(nm\log{k})\)。
代码
#include<bits/stdc++.h>
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
int ch=getchar();
T f=1;x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x*=f;rd(args...);
}
#define pii std::pair<int,int>
#define fir first
#define sec second
typedef long long ll;
const int N=6e5+5;
int T,n,m,k;
std::map<int,int> mp[N];
struct node{ll val,tg,mx;}t[N<<2];
inline void Addtag(int i,ll tg,ll mx){
t[i].val=std::max(t[i].val,mx)+tg;
t[i].mx=std::max(t[i].mx,mx-t[i].tg);
t[i].tg+=tg;
}
inline void PushDown(int i){
if(t[i].tg||t[i].mx){
Addtag(i*2,t[i].tg,t[i].mx);
Addtag(i*2+1,t[i].tg,t[i].mx);
t[i].tg=t[i].mx=0;
}
}
inline void PushUp(int i){
t[i].val=std::max(t[i*2].val,t[i*2+1].val);
}
void Build(int i,int l,int r){
t[i].tg=t[i].mx=t[i].val=0;
if(l==r)return;
int mid=(l+r)>>1;
Build(i*2,l,mid);Build(i*2+1,mid+1,r);
}
void Update(int i,int l,int r,int x,ll v){
if(l==r)return t[i].val+=v,void();
int mid=(l+r)>>1;PushDown(i);
if(x<=mid)Update(i*2,l,mid,x,v);
else Update(i*2+1,mid+1,r,x,v);
PushUp(i);
}
inline void Solve(){
rd(n,m,k);
Build(1,1,k);
for(int i=1;i<=n;i++){
mp[i].clear();
for(int j=1;j<=m;j++){
int x;rd(x);
++mp[i][x];
}
if(i==1)continue;
for(pii p:mp[i]){
if(p.fir<0)continue;
Addtag(1,1ll*p.sec*mp[i-1][p.fir],0);
Update(1,1,k,p.fir,1ll*p.sec*mp[i-1][-1]);
}
ll tmp=t[1].val;
Addtag(1,1ll*mp[i][-1]*mp[i-1][-1],0);
Addtag(1,0,tmp);
for(pii p:mp[i-1]){
if(p.fir<0)continue;
Update(1,1,k,p.fir,1ll*p.sec*mp[i][-1]);
}
}
printf("%lld\n",t[1].val);
}
signed main(){
rd(T);
while(T--)Solve();
return 0;
}