60分代码求助
查看原帖
60分代码求助
563163
ligangyi楼主2021/11/10 07:28
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAXN = 55;

int w[MAXN][MAXN], f[MAXN * 2][MAXN][MAXN], n, m;

int main(){
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            scanf("%d", &w[i][j]);
        }
    }
    f[2][1][1] = 0;
    for(int k = 3; k <= m + n; k++){
        for(int i1 = 1; i1 <= m; i1++){
            for(int i2 = 1; i2 <= m; i2++){
                int j1 = k - i1, j2 = k - i2;
                int t = w[i1][j1];
                if(i1 != i2){
                    t += w[i2][j2];
                }
                if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n){
                    int &x = f[k][i1][i2];
                    x = max(x, f[k - 1][i1][i2] + t);
                    x = max(x, f[k - 1][i1 - 1][i2] + t);
                    x = max(x, f[k - 1][i1][i2 - 1] + t);
                    x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
                }
            }
        }
    }
    printf("%d", f[m + n][m][n]);
    return 0;
}
2021/11/10 07:28
加载中...