洛谷P 2706チョコレート
1161 ワード
タイトルリンク:link
この問題はすべての
どのように最大のサブマトリクスを求めてインターネットで調べることができるか分からないので、たくさんつかんでいます.
注意
Code:\texttt{Code:} Code:
パクリしないで、転載して出典を明記してください.
見てくれてありがとう!
この問題はすべての
0
を-inf
(inf=0 x 3 f 3 f 3 f 3 f)に設定し、その後最大サブマトリクス和を求めることが容易に考えられる.どのように最大のサブマトリクスを求めてインターネットで調べることができるか分からないので、たくさんつかんでいます.
注意
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;
}
パクリしないで、転載して出典を明記してください.
見てくれてありがとう!