PAT NC220014. 2 最强对手矩阵
原题链接
中等
作者:
QAQ_ning
,
2021-04-14 21:17:33
,
所有人可见
,
阅读 217
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int n,m;
ll ans;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n>>m;
vector<vector<int>> a(n+1,vector<int>(m+1));
//题目并没有说明n、m的具体范围,当然是开动态数组最好
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
if(m<n)
{
vector<vector<int>> b(m+1,vector<int>(n+1));
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
b[i][j]=a[j][i]; //反转整个矩阵
b[i][j]+=b[i-1][j]; //计算列前缀和
}
swap(n,m);
for(int i=1;i<=n;i++) //枚举竖边的起点
for(int j=i;j<=n;j++) //枚举竖边的终点
{
ll tot=0;
//当枚举了竖边,那我们就相当于把竖边的和当作一个已知数了
//那现在就可以把他看成一个求横边的最大子序列和问题啦
for(int k=1;k<=m;k++)
{
if(tot<0) tot=0;
tot+=b[j][k]-b[i-1][k];
ans=max(ans,tot);
}
}
}
else
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]+=a[i-1][j]; //这种就少一个反转操作,直接计算前缀和就行
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
{
ll tot=0;
for(int k=1;k<=m;k++)
{
if(tot<0) tot=0;
tot+=a[j][k]-a[i-1][k];
ans=max(ans,tot);
}
}
}
cout<<ans;
return 0;
}