20pts仅AC#2,#5,#8,#16,Subtask#1玄关
查看原帖
20pts仅AC#2,#5,#8,#16,Subtask#1玄关
1235819
_std_xzh楼主2024/10/19 20:47
#include<bits/stdc++.h>
using namespace std;
int n , m , a[1005][1005] , ans[1005][1005] , dp[1005][1005] , dp2[1005][1005];
int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++)cin >> a[i][j];
    }
    for(int i = 1;i <= n;i++)ans[i][1] += a[i][1];
    for(int i = 1;i <= m;i++)dp[1][i] = dp[1][i - 1] + a[1][i] , dp2[n][i] = dp2[n][i - 1] + a[n][i];
    for(int i = 1;i <= m;i++){
        for(int j = 1;j <= n;j++)dp[j][i] = max(dp[j - 1][i] , ans[j][i - 1]) + a[j][i];
        for(int j = n;j >= 1;j--)dp2[j][i] = max(dp2[j + 1][i] , ans[j][i - 1]) + a[j][i];
        for(int j = 1;j <= n;j++)ans[j][i] = max(dp[j][i] , dp2[j][i]);
    }
    cout << ans[n][m];
    return 0;
}
2024/10/19 20:47
加载中...