DZY Loves Modification

Hisaishi_Kanade · 2023-02-24 20:15:39 · 题解

首先，想到一个很神秘的贪心：每次挑出和最大的一行或一列，对其进行操作。

但是它是错的。

那么这是否给了我们启发，行列一起贪心不可行，那我分开贪心呢？

我们设立两个辅助数组，初始 row_{i}=\sum\limits_{j=1}^m a_{i,j}，col_{j}=\sum\limits_{i=1}^n a_{i,j}。

定义 f_{0,i} 表示在不考虑列的情况下，对行进行 i 次操作所得最大分数。

显然 f_{0,0}=0 考虑如何求出 f_{0,1},f_{0,2},\cdots,f_{0,k-1},f_{0,k}。

不难想到一个贪心策略，每次在 row 数组中找到最大的值 row_{pos} 转移 f_{0,i}=f_{0,i-1}+row_{pos}，再对这一行操作——即 row_{pos}\gets row_{pos}-m\times p。

类似地定义 f_{1,i} 表示在不考虑行的情况下，对列进行 i 次操作所得最大分数。类似地用 col 转移。

发现需要一个快速找到最大值，对最大值进行修改的数据结构，堆就可以胜任。

最后考虑如果从 f_{0/1,i} 推得答案。

容易发现，i 行 k-i 列的相交次数共有 i\times(k-i) 个，则 ans=\max\{f_{0,i}+f_{1,k-i}-i\times(k-i)\times p\}。

#include <queue>
#include <vector>
#include <algorithm>
int n,m,k,p,i,j;
std::priority_queue<long long> q;
long long f[2][1000005],row[1005],col[1005],a[1005][1005];
int main()
{
    int t=1;
    while(t--)
    {
        long long ret=-(1ll<<60),delta,mid;
        n=read();m=read();
        k=read();p=read();
        for(i=1;i<=k;++i)
            f[0][i]=f[1][i]=0;
        for(i=1;i<=n;++i)
            row[i]=0;
        for(i=1;i<=m;++i)
            col[i]=0;
        for(i=1;i<=n;++i)
            for(j=1;j<=m;++j)
                a[i][j]=read();
        for(i=1;i<=n;++i)
            for(j=1;j<=m;++j)
                row[i]+=a[i][j];
        for(i=1;i<=n;++i)
            for(j=1;j<=m;++j)
                col[j]+=a[i][j];
        while(!q.empty())
            q.pop();
        for(i=1;i<=n;++i)
        {
            q.push(row[i]);
        }
        delta=m*p;
        for(i=1;i<=k;++i)
        {
            f[0][i]=f[0][i-1]+q.top();
            mid=q.top();
            q.pop();
            q.push(mid-delta);
//          printf("%lld\n",q.top());
        }
        while(!q.empty())
            q.pop();
        for(i=1;i<=m;++i)
        {
            q.push(col[i]);
        }
        delta=n*p;
        for(i=1;i<=k;++i)
        {
            f[1][i]=f[1][i-1]+q.top();
            mid=q.top();
            q.pop();
            q.push(mid-delta);
        }
        for(i=0;i<=k;++i)
        {
            ret=std::max(ret,f[0][i]+f[1][k-i]-1ll*i*(k-i)*p);
        }
        printf("%lld\n",ret);
    }
    return 0;
}