洛谷P 2706チョコレート


タイトルリンク:link
この問題はすべての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;
}

パクリしないで、転載して出典を明記してください.
見てくれてありがとう!