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;
}