wlxsq的专栏通过本文主要向大家介绍了skin to the max,m.c the max李秀,ski to the max,mc the max,the max等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1081
/*
将维度合成一列
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1050;
int dp[N][N]; // dp[i][j]表示从dp[1][j]~dp[i][j]的和
int a[N][N];
int t[N];
int ss,ee;
int MaxSum(int *a,int n)
{
int s;
int Max=0,sum=0;
for(int i=1;i<=n;i++){
if(sum>0){
sum+=a[i];
}else{
s=i;
sum=a[i];
}
if(sum>Max){
Max=sum;
ss=s;
ee=i;
}
}
return Max;
}
int main()
{
int n;
while(cin>>n){
memset(dp,0,sizeof(dp));
memset(t,0,sizeof(t));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
dp[i][j]=dp[i-1][j]+a[i][j];
}
}
int Max=0;
int x,y,S,T; // 开始行，宽度，开始结束位置
for(int i=1;i<=n;i++){ // 枚举行的起点
for(int j=1;j<=n-i+1;j++){ // 枚举宽度
for(int k=1;k<=n;k++){ // 枚举列,将二维整合成一维
t[k]=(dp[i+j-1][k]-dp[i-1][k]);
}
int tmp=MaxSum(t,n);
if(tmp>Max){
Max=tmp;
x=i;
y=j;
S=ss;
T=ee;
}
}
}
cout<<Max<<endl;
// for(int i=x;i<=x+y-1;i++){
// for(int j=S;j<=T;j++){
// cout<<a[i][j]<<' ';
// }
// cout<<endl;
// }
}
return 0;
}