nyoj 104 最大和 51nod oj 1051 最大子矩阵和 【DP】

问题与“最大子段和”是一样的-.-

最大字段和：用dp[i]记录以i结尾的最大和--

if（dp[i-1]<=0） dp[i]=shu[i];

else dp[i]=dp[i-1]+shu[i];

只是一维变二维---我们可以枚举高度--再按照一维来写

题目链接：104

代码：

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define LL long long LL shu[600][600]; LL he[600][600]; int main() { int m,n,t;scanf("%d",&t); while (t--) { scanf("%d%d",&n,&m); memset(he,0,sizeof(he)); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%lld",&shu[i][j]); for (int j=1;j<=m;j++) { he[0][j]=0; for (int i=1;i<=n;i++) he[i][j]=he[i-1][j]+shu[i][j]; } LL ans=-99999999,s; for (int i=1;i<=n;i++) { for (int j=i;j<=n;j++) { s=0; for (int k=1;k<=m;k++) { if (s<0) s=he[j][k]-he[i-1][k]; else s+=he[j][k]-he[i-1][k]; ans=max(ans,s); } } } printf("%lld\n",ans); } return 0; }

题目链接：1051

代码：

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define LL long long LL shu[600][600]; LL he[600][600]; int main() { int m,n; scanf("%d%d",&m,&n); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%lld",&shu[i][j]); for (int j=1;j<=m;j++) { he[0][j]=0; for (int i=1;i<=n;i++) he[i][j]=he[i-1][j]+shu[i][j]; } LL ans=0,s; for (int i=1;i<=n;i++) { for (int j=i;j<=n;j++) { s=0; for (int k=1;k<=m;k++) { if (s<0) s=he[j][k]-he[i-1][k]; else s+=he[j][k]-he[i-1][k]; ans=max(ans,s); } } } printf("%lld\n",ans); return 0; }