我们注意到 || solution - CF2053F

· · 题解

我们注意力惊人。

Solution

显然有一个显然的结论：一行只能填同一种数，因为对于一个位置，填上一行加下一行出现次数最多的数一定不比填别的数更劣。

先不管复杂度，列出一个朴素的方程，设 f_{i,j} 为只考虑前 i 行，第 i 行填 j 的答案，则考虑上一行填的数是否与这一行相同，设 c_{i,j} 为第 i 行已经确定的数中 j 的个数，d_i 为第 i 行空位的个数，则有：

f_{i,j} = \max _x (f_{i-1,x} + [x=j] \times d_i d_{i-1}) + d_i \times (c_{i-1,j} + c_{i+1,j})

但是这样复杂度 O(nk) 是爆炸的，我们注意到（？）可以只维护 f_j，用某种方式进行 i-1 \to i 的转移。

我们再次注意到（！），上面的式子可以拆成三个操作：

可以直接线段树，但是我们讨厌 ds，于是我们再再次注意到（……），操作一可以维护全局加法 tag，操作二可以维护全局最大值 tag，操作三需要支持单点加，可以直接用关于加法 tag 的偏移量解决。最后最大值为全局最大值 tag 和每一次单点加后的最大值的最大值。

Code

int n,m,k;
vector < vector<int> > a;
int d[MAXN],c[MAXN];

class segtree
{
public:
    int f[MAXN],maxtag=0,addtag=0,mx=0;

    il void clr()
    {
        rep(i,0,k+1) f[i]=0;
        maxtag=addtag=mx=0;
    }

    il void alladd(int k)
    {
        maxtag+=k,addtag+=k;
    }

    il void allmax(int k)
    {
        maxtag=max(maxtag,k);
    }

    il void add(int p,int k)
    {
        f[p]=max(f[p],maxtag-addtag)+k;
        mx=max(mx,f[p]);
    }

    il int q()
    {
        return max(mx+addtag,maxtag);
    }
} tr;

il void solve(int __Ti)
{
    clr(a);

    read(n,m,k);

    tr.clr();
    rep(i,0,max(n,k)+1) d[i]=c[i]=0;

    a.resize(n+5);
    rep(i,0,n+1) a[i].resize(m+5);
    rep(i,1,n) rep(j,1,m) read(a[i][j]),a[i][j]==-1 && (++d[i]);

    int ans=0;
    rep(i,1,n)
    {
        rep(j,1,m) a[i][j]!=-1 && (c[a[i][j]]=0);
        rep(j,1,m) i-1>=1 && a[i-1][j]!=-1 && (++c[a[i-1][j]]);
        rep(j,1,m) a[i][j]!=-1 && (ans+=c[a[i][j]]);
    }

    int qwq;
    rep(i,1,n)
    {
        qwq=tr.q();
        tr.alladd(d[i-1]*d[i]);
        tr.allmax(qwq);

        rep(j,1,m)
        {
            i-1>=1 && a[i-1][j]!=-1 && (tr.add(a[i-1][j],d[i]),1);
            i+1<=n && a[i+1][j]!=-1 && (tr.add(a[i+1][j],d[i]),1);
        }
    }

    write(ans+tr.q(),'\n');
}

但是呢，由于我们注意力惊人，所以直接输出「华风夏韵 洛水天依」不可以 AC 此题。