P5761 题解

Gaode_Sean · 2022-02-12 16:39:09 · 题解

对于这道题，先求出每一列的最大值，注意初始化为负无穷而不是 0 。

设每一行的最大值为 a_i，dp_i 表示以 a_i 为结尾的最大字段和。

转移方程：dp_i=\max(0,dp_{i-1})+a_i 。

最后的答案即是 =\max{dp_i}

Code:

#include<bits/stdc++.h>
using namespace std;
int n,m,a[101][20001],b[20001],dp[20001],ans,mx;
int main()
{
    cin>>n>>m;
    m--;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) cin>>a[i][j];
    }
    for(int i=1;i<=m;i++) b[i]=-1e9;
    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++) b[j]=max(b[j],a[i][j]);
    }
    for(int i=1;i<=m;i++){
        dp[i]=max(mx,dp[i-1])+b[i];
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0; 
}