CF446B DZY Loves Modification（优先队列）

本来想对行列都维护线段树，然后每次查询两棵的最大值，之后进行修改。但是要考虑很多问题，例如最大值相同的时候选哪个，这些细节操作起来十分复杂，我也不知道是否可行

有一种巧妙的思路，我们发现取行对于取其他行没有影响，只对当前行有影响。因此就是用优先队列来分别计算选i次行，i次列的答案。

之后枚举选行的次数进行算。这里有行列重复的答案，只需要减去这么多个p即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
const int mod=1e9+7;
int a[1010][1010];
ll s[1010][1010];
ll d[1010][1010];
ll ans1[N];
ll ans2[N];
ll n,m,k,p;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>k>>p;
    int i,j;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            cin>>a[i][j];
            s[i][j]=s[i][j-1]+a[i][j];
        }
    }
    for(int i=1;i<=m;i++){
        for(j=1;j<=n;j++){
            d[j][i]=d[j-1][i]+a[j][i];
        }
    }
    priority_queue<ll> q1;
    priority_queue<ll> q2;
    for(i=1;i<=n;i++){
        q1.push(s[i][m]);
    }
    for(i=1;i<=m;i++){
        q2.push(d[n][i]);
    }
    for(i=1;i<=k;i++){
        auto x=q1.top();
        q1.pop();
        ans1[i]=ans1[i-1]+x;
        x-=(ll)m*p;
        q1.push(x);
    }
    for(i=1;i<=k;i++){
        auto x=q2.top();
        q2.pop();
        ans2[i]=ans2[i-1]+x;
        x-=(ll)n*p;
        q2.push(x);
    }
    ll res=-1e18;
    for(i=0;i<=k;i++){
        res=max(res,ans1[i]+ans2[k-i]-1ll*i*(k-i)*p);
    }
    cout<<res<<endl;
    return 0;
}

View Code

CF446B DZY Loves Modification（优先队列）

推荐阅读