题目链接:link
这题很容易想出来把所有 0
设为 -inf
(inf=0x3f3f3f3f) ,之后求最大子矩阵和。
不知道怎么求最大子矩阵和可以上网查,一抓一大把(
注意使用 long long
, 作者比较懒就用了 #define int long long
,把intmain()
改为 signed main()
即可~
Code: \texttt{Code:} Code:
#include
using namespace std;
#define int long long
const int N=310,inf=0x3f3f3f3f;
int n,m,g[N][N],ans,f[N],h[N][N];
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;
i<=n;
i++)
for(int j=1;
j<=m;
j++)
{
scanf("%lld",&g[i][j]);
g[i][j]=(g[i][j]==0?-inf:g[i][j]);
h[i][j]=h[i-1][j]+g[i][j];
}
for(int i=1;
i<=n;
i++)
for(int j=i;
j<=n;
j++)
{
int res=0;
for(int k=1;
k<=m;
k++)
f[k]=f[k-1]+h[j][k]-h[i-1][k];
for(int k=1;
k<=m;
k++)
ans=max(ans,f[k]-res),res=min(f[k],res);
}
printf("%lld",ans);
return 0;
}
请勿抄袭,转载请标明出处。
【C++题解|洛谷 P2706 巧克力 题解】感谢观看!