51nod 1051【基础】

思路：

找题4级做做。。。然后找了题最水的。。

= =感动。。。居然是一下子【记】得了做法。。。

dp一下，枚举列的起点和终点，然后求和这一段，然后对这一大列就是求个最大字段和；

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=5e2+10;

LL a[N][N];

LL sum[N][N];

LL temp[N];

int n,m;

LL max_ele()

{

    LL d=temp[1];

    LL ans=temp[1];

    for(int i=2;i<=n;i++)

    {

        if(d<0)

            d=temp[i];

        else

            d+=temp[i];

        ans=max(d,ans);

    }

    return ans;

}

void init(int s,int t)

{

    for(int i=1;i<=n;i++)

        temp[i]=sum[i][t]-sum[i][s-1];

}

int main()

{

    scanf("%d%d",&m,&n);

    memset(sum,0,sizeof(sum));

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

        {

            scanf("%lld",&a[i][j]);

            sum[i][j]=a[i][j]+sum[i][j-1];

        }

    LL ans=0;

    for(int s=1;s<=m;s++)

    {

        for(int t=s;t<=m;t++)

        {

            init(s,t);

            ans=max(ans,max_ele());

        }

    }

    printf("%lld\n",ans);

    return 0;

}

巴特西

51nod 1051【基础】

最新文章

热门文章