SSL_1517【キャンディボックス】
9844 ワード
キャンディボックス
タイトル
n*m個の格子に分けられたキャンディボックスで、i行目j列目の格子にはa[i][j]粒の糖が入っています.もともとtenshiはこのキャンディをあるPPMMに送るつもりだったが、キャンディボックスを送る前日の夜、極めて憎らしいネズミがキャンディボックスを夜襲し、一部の格子が略奪され穴を開けた.tenshiはできるだけ早くこのキャンディボックスから矩形のキャンディボックスを切断しなければならない.新しいキャンディボックスには穴が開けられず、tenshiは新しいキャンディボックスに残っている砂糖の総数をできるだけ多くしたいと思っている.tenshiのプログラムを設計して、新しいキャンディボックスがどれだけのキャンディを残すことができるかを計算してください.
入力
ファイルからINデータを読み込みます.最初の行には2つの整数n,mがある.i+1行目のj番目の数はa[i][j]を表し,この数が0であれば,この位置を表す格子が略奪された.そのうち:1≦n,m≦300≦a[i][j]≦255
しゅつりょく
最大キャンディ数をCANDYに出力.OUT.
Sample Input
Sample Output
注:10 3 4この矩形のキャンディの数が最大です
解析
tenshiは実力で独身で、ネズミに襲われたキャンディはPPMM安屠生に毎日寝る前の小さな事故を与えることができます:tenshiを襲ったキャンディのネズミには新型コロナウイルスが含まれていると噂されていますが、tenshiは最初の感染者の本題です.私たちは0ごとに極小の数に修正することができます.他の値が255であってもゼロを下回ることはできません.これでタイトルが最大行列和になった(ブログ転送ゲート:SSL_1205【最大サブ行列の和】)
コード#コード#
タイトル
n*m個の格子に分けられたキャンディボックスで、i行目j列目の格子にはa[i][j]粒の糖が入っています.もともとtenshiはこのキャンディをあるPPMMに送るつもりだったが、キャンディボックスを送る前日の夜、極めて憎らしいネズミがキャンディボックスを夜襲し、一部の格子が略奪され穴を開けた.tenshiはできるだけ早くこのキャンディボックスから矩形のキャンディボックスを切断しなければならない.新しいキャンディボックスには穴が開けられず、tenshiは新しいキャンディボックスに残っている砂糖の総数をできるだけ多くしたいと思っている.tenshiのプログラムを設計して、新しいキャンディボックスがどれだけのキャンディを残すことができるかを計算してください.
入力
ファイルからINデータを読み込みます.最初の行には2つの整数n,mがある.i+1行目のj番目の数はa[i][j]を表し,この数が0であれば,この位置を表す格子が略奪された.そのうち:1≦n,m≦300≦a[i][j]≦255
しゅつりょく
最大キャンディ数をCANDYに出力.OUT.
Sample Input
3 4
1 2 3 4
5 0 6 3
10 3 4 0
Sample Output
17
注:10 3 4この矩形のキャンディの数が最大です
解析
tenshiは実力で独身で、ネズミに襲われたキャンディはPPMM安屠生に毎日寝る前の小さな事故を与えることができます:tenshiを襲ったキャンディのネズミには新型コロナウイルスが含まれていると噂されていますが、tenshiは最初の感染者の本題です.私たちは0ごとに極小の数に修正することができます.他の値が255であってもゼロを下回ることはできません.これでタイトルが最大行列和になった(ブログ転送ゲート:SSL_1205【最大サブ行列の和】)
コード#コード#
#include
#include
#include
using namespace std;
int a[1001][1001],b[1001],s[1001][1001],n,m,maxn=0;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]==0)a[i][j]=-23040000;
s[i][j]=s[i-1][j]+a[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
int sum=0;
for(int k=1;k<=m;k++)b[k]=s[j][k]-s[i-1][k];
for(int k=1;k<=m;k++)
{
sum+=b[k];
maxn=max(maxn,sum);
if(sum<0)sum=0;
}
}
}
if(maxn<=0)cout<<"NO";
else cout<<maxn;
return 0;
}