CF1219G Harvester 题解

FFTotoro · 2022-12-06 22:08:45 · 题解

前言

分类讨论好题 & 100 蓝 AC 祭。

解法

首先，因为我们只能确定 N\times M 的范围，所以数组需要使用 std::vector 存储。

其次，用数组 s_1,s_2 分别维护每一行、每一列的泡泡的数量总和；

接着，容易观察到，本题的最大值可能有 5 种情况：

• 选择 4 行；
• 选择 4 列；
• 选择 3 行 1 列；
• 选择 3 列 1 行；
• 选择 2 行 2 列。

对于前两种情况，只需要从预处理出的 s_1,s_2 中分别选择出最大的四个相加就可以了；

对于三、四种情况，确定那唯一的 1 行 / 1 列，再从剩下的列 / 行中选择出减去它与那唯一的 1 行 / 1 列交界处的泡泡（容斥原理）的三个最大的相加；

对于第五种情况，判断一下 N 和 M 的大小关系：

• 若 N>M，我们就枚举那两个列，接着按照类似三、四中的方法选出去除交点后总和最大的两列相加；
• 否则，枚举两个行，然后再选出两个去除交点后总和最大的两行相加；

五种情况取最大值即可。

对于每一种情况，中间取最大的若干个值可以使用优先队列维护。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
  int n,m; cin>>n>>m;
  vector<vector<int> > a(n,vector<int>(m));
  vector<int> s(n),s2(m),r(8);
  for(auto &i:a)for(auto &j:i)cin>>j;
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
      s[i]+=a[i][j],s2[j]+=a[i][j];
  priority_queue<int> q[2];
  for(auto &i:s)q[0].emplace(i);
  for(int i=1;i<=4&&!q[0].empty();i++)
    r[0]+=q[0].top(),q[0].pop();
  for(auto &i:s2)q[1].emplace(i);
  for(int i=1;i<=4&&!q[1].empty();i++)
    r[1]+=q[1].top(),q[1].pop();
  for(int i=0;i<n;i++){
    priority_queue<int> p;
    for(int j=0;j<m;j++)
      p.emplace(s2[j]-a[i][j]);
    r[5]=s[i]; for(int i=1;i<=3&&!p.empty();i++)
      r[5]+=p.top(),p.pop();
    r[2]=max(r[2],r[5]);
  }
  for(int i=0;i<m;i++){
    priority_queue<int> p;
    for(int j=0;j<n;j++)
      p.emplace(s[j]-a[j][i]);
    r[5]=s2[i]; for(int i=1;i<=3&&!p.empty();i++)
      r[5]+=p.top(),p.pop();
    r[3]=max(r[3],r[5]);
  }
  if(n>m){
    for(int i=0;i<m-1;i++)
      for(int j=i+1;j<m;j++){
        priority_queue<int> p;
        for(int k=r[5]=0;k<n;k++)
          p.emplace(s[k]-a[k][i]-a[k][j]);
        for(int i=1;i<=2&&!p.empty();i++)
          r[5]+=p.top(),p.pop();
        r[4]=max(r[4],r[5]+s2[i]+s2[j]);
      }
  }
  else{
    for(int i=0;i<n-1;i++)
      for(int j=i+1;j<n;j++){
        priority_queue<int> p;
        for(int k=r[5]=0;k<m;k++)
          p.emplace(s2[k]-a[i][k]-a[j][k]);
        for(int i=1;i<=2&&!p.empty();i++)
          r[5]+=p.top(),p.pop();
        r[4]=max(r[4],r[5]+s[i]+s[j]);
      }
  }
  cout<<*max_element(r.begin(),r.end())<<endl;
  return 0;
}