CF1219G Harvester 題解

（從luogu上搬過來了！）

[Harvester題面]

個人感覺這題在綠題范圍

題面描述

n * m的網格中，在第i行j列有a[i][j]個泡泡，每次可以收割一行或一列的泡泡，最多可以收割4次，問最多可以收割到多少泡泡，

分析

1.錯誤的想法①

拿到題面，我首先的思路是一個簡易的模擬：

直接讀入二維陣列，首先用前綴和統計每一行和每一列的總和

for(ll i=1;i<=n;i++)
{
    for(ll j=1;j<=m;j++)
    {
        cin>>a[i][j];
        xx[i]+=a[i][j];
        yy[j]+=a[i][j];
    }
}

再在行和列中找到當前收割走此行/列后可以得到最多泡泡的行/列，每次收割走就把它會影響到的行/列處理一下

具體例子如第二個樣例

5 5

0 9 2 7 0

9 0 3 0 5

0 8 0 3 1

6 7 4 3 9

3 6 4 1 0

第一次我們拿了第四行(xx[4])，所以要把所有列的前綴和都減去a[4][j],以防重復添加，

然后再重復四次，

提交后，驚奇地發現，第四個點就WA了，why？

這種想法很顯然是錯誤的，當我們發現某行取走能得到當前的最大值，然后取了這行之后會把所有列都減小，但是有可能此時取要多個列更優，即這種模擬做法可能會失去最大的結果

2.錯誤的想法②

既然會失去某些結果，那要不就在上一種代碼的思路上dfs把所有能取的方法走一遍

但是，顯而易見這種 的復雜度會炸掉（提交后第4個點就TLE了）

3.正解

那么這條路看起來已經走到頭了，所以正解要怎么搞！？

不妨換一種思路,既然只有四次取泡泡的機會，那取的方案應該只有5種：

1.取四行

2.取四列

3.取一行三列

4.取一列三行

5.取兩行兩列

那么我們只要矩陣中分別以以上5種方法計算一遍取最大值就可以了！

對于第1種方案，只需把所有行排序一下并把最大的四行加起來就行（當然不排序直接找最大四行也是可以的），復雜度，

for(ll i=1;i<=n;i++) xxx[i]=xx[i];
sort(xxx+1,xxx+n+1,cmp);
for(ll i=1;i<=4;i++) sum+=xxx[i];
ll maxx=sum

對于第2種方案，同上，

for(ll i=1;i<=m;i++) yyy[i]=yy[i];
sort(yyy+1,yyy+m+1,cmp);
for(ll i=1;i<=4;i++) sum+=yyy[i];
maxx=max(maxx,sum);

對于第3種方案，先選擇一行，再在所有列里面找最大的三列，復雜度，

for(ll i=1;i<=n;i++)
    {
        ll max1=0,max2=0,max3=0;
        for(ll j=1;j<=m;j++)
        {
            yyy[j]=yy[j]-a[(i-1)*m+j];
            if(yyy[j]>=max1) max3=max2,max2=max1,max1=yyy[j]; else 
            if(yyy[j]>=max2) max3=max2,max2=yyy[j]; else
            if(yyy[j]>=max3) max3=yyy[j];
        } 
        sum=max1+max2+max3+xx[i];
        maxx=max(maxx,sum);
    }

對于第4種方案，同上，

for(ll i=1;i<=m;i++)
    {
        ll max1=0,max2=0,max3=0;
        for(ll j=1;j<=n;j++)
        {
            xxx[j]=xx[j]-a[(j-1)*m+i];
            if(xxx[j]>=max1) max3=max2,max2=max1,max1=xxx[j]; else 
            if(xxx[j]>=max2) max3=max2,max2=xxx[j]; else
            if(xxx[j]>=max3) max3=xxx[j];
        } 
        sum=max1+max2+max3+yy[i];
        maxx=max(maxx,sum);
    }

對于第5種方案，先用兩個回圈固定兩行，再在所有列里面找最大的兩列，復雜度

for(ll i=1;i<n;i++)
     {
         for(ll j=i+1;j<=n;j++)
         {
             ll max1=0,max2=0;
             for(ll k=1;k<=m;k++)
             {
                 yyy[k]=yy[k]-a[(i-1)*m+k]-a[(j-1)*m+k];
                if(yyy[k]>=max1) max2=max1,max1=yyy[k]; else 
                if(yyy[k]>=max2) max2=yyy[k]; 
            }
            sum=max1+max2+xx[i]+xx[j];
            maxx=max(maxx,sum);
        }
    }

在上面五種方案里選最大的那個就是答案了

本題注意點

1.因為n*m<=，所以這里可以把二維陣列壓成一維來儲存，把原來的儲存在中

for(ll i=1;i<=n;i++)
    for(ll j=1;j<=m;j++)
    {
        cin>>a[(i-1)*m+j];
        xx[i]+=a[(i-1)*m+j];
        yy[j]+=a[(i-1)*m+j];
    }

2.對于第五種方案的時間復雜度，很可能會超時（實測第6個點TLE了），

所以在n>m 時，我們把整個陣列旋轉90°，即把nm互換，

if(n>m)
    { 
        for(ll i=1;i<=n;i++)
            for(ll j=1;j<=m;j++)
                b[(j-1)*n+i]=a[(i-1)*m+j];
        swap(n,m);
        for(ll i=1;i<=n;i++)
            for(ll j=1;j<=m;j++)
                a[(i-1)*m+j]=b[(i-1)*m+j];
    }

完整代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=100010;
unsigned long long ans,anss;
ll n,m;
ll xx[maxn],yy[maxn],xxx[maxn],yyy[maxn],a[maxn],b[maxn];
ll tt[5],rt[5];
bool cmp(ll x,ll y) {return x>y;}
ll work()
{
    ll sum=0;
    for(ll i=1;i<=n;i++) xxx[i]=xx[i];
    sort(xxx+1,xxx+n+1,cmp);
    for(ll i=1;i<=4;i++) sum+=xxx[i];
    ll maxx=sum;
    sum=0;
//    cout<<maxx<<endl;
    
    for(ll i=1;i<=m;i++) yyy[i]=yy[i];
    sort(yyy+1,yyy+m+1,cmp);
    for(ll i=1;i<=4;i++) sum+=yyy[i];
    maxx=max(maxx,sum);
    sum=0;
//    cout<<maxx<<endl;
    
    for(ll i=1;i<=n;i++)
    {
        ll max1=0,max2=0,max3=0;
        for(ll j=1;j<=m;j++)
        {
            yyy[j]=yy[j]-a[(i-1)*m+j];
            if(yyy[j]>=max1) max3=max2,max2=max1,max1=yyy[j]; else 
            if(yyy[j]>=max2) max3=max2,max2=yyy[j]; else
            if(yyy[j]>=max3) max3=yyy[j];
        } 
        sum=max1+max2+max3+xx[i];
        maxx=max(maxx,sum);
    }
    sum=0;
//    cout<<maxx<<endl;
    
    for(ll i=1;i<=m;i++)
    {
        ll max1=0,max2=0,max3=0;
        for(ll j=1;j<=n;j++)
        {
            xxx[j]=xx[j]-a[(j-1)*m+i];
            if(xxx[j]>=max1) max3=max2,max2=max1,max1=xxx[j]; else 
            if(xxx[j]>=max2) max3=max2,max2=xxx[j]; else
            if(xxx[j]>=max3) max3=xxx[j];
        } 
        sum=max1+max2+max3+yy[i];
        maxx=max(maxx,sum);
    }
    sum=0;
//    cout<<maxx<<endl;
    
    if(n>m)
    { 
        for(ll i=1;i<=n;i++)
            for(ll j=1;j<=m;j++)
                b[(j-1)*n+i]=a[(i-1)*m+j];
        swap(n,m);
        for(ll i=1;i<=n;i++)
            for(ll j=1;j<=m;j++)
                a[(i-1)*m+j]=b[(i-1)*m+j];
    }
     for(ll i=1;i<n;i++)
     {
         for(ll j=i+1;j<=n;j++)
         {
             ll max1=0,max2=0;
             for(ll k=1;k<=m;k++)
             {
                 yyy[k]=yy[k]-a[(i-1)*m+k]-a[(j-1)*m+k];
                if(yyy[k]>=max1) max2=max1,max1=yyy[k]; else 
                if(yyy[k]>=max2) max2=yyy[k]; 
            }
//            cout<<max1<<' '<<max2<<' '<<xx[i]<<' '<<xx[j]<<endl;
            sum=max1+max2+xx[i]+xx[j];
            maxx=max(maxx,sum);
        }
    }
    return maxx;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=m;j++)
        {
            cin>>a[(i-1)*m+j];
            xx[i]+=a[(i-1)*m+j];
            yy[j]+=a[(i-1)*m+j];
        }
    }
    cout<<work()<<endl;
    return 0;
}