题面描述
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把所有能取的方法走一遍
但是，显而易见这种$O(C_{n+m}^4)$的复杂度会炸掉（提交后第4个点就TLE了）
3.正解
那么这条路看起来已经走到头了，所以正解要怎么搞！？
不妨换一种思路,既然只有四次取泡泡的机会，那取的方案应该只有5种：
1.取四行
2.取四列
3.取一行三列
4.取一列三行
5.取两行两列
那么我们只要矩阵中分别以以上5种方法计算一遍取最大值就可以了！
对于第1种方案，只需把所有行排序一下并把最大的四行加起来就行（当然不排序直接找最大四行也是可以的），复杂度$O(NlogN)$。
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种方案，先选择一行，再在所有列里面找最大的三列，复杂度$O(NM)$。
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种方案，先用两个循环固定两行，再在所有列里面找最大的两列，复杂度$O(N^2M)$
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.因为$nm<=10^5$ ，所以这里可以把二维数组压成一维来储存，把原来的$a[i][j]$储存在$a[(i-1)m+j]$中
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.对于第五种方案$O(NNM)$的时间复杂度，很可能会超时（实测第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;
}
0 条评论