题目

同 acwing 275 传纸条 题解

特殊：如何改用稀疏图存储并遍历矩阵（存储方格中的数的矩阵）

代码

注意：最后得到的答案是路径上的答案，要加上起点(1, 1)和终点(n, n)。

#include<iostream>

#define _rep_le(i, a, b) for(int i = (a); i <= (b); ++ i)
#define _rep_lt(i, a, b) for(int i = (a); i < (b); ++ i)
#define _rrep_ge(i, a, b) for(int i = (b); i >= (a); -- i)
#define _rrep_gt(i, a, b) for(int i = (b); i > (a); -- i)

#define MAX(a, b, c, d) max(max((a), (b)), max((c), (d)))

using namespace std;

const int N = 1e1 + 5;

int arc[N][N];
int f[N+N][N][N];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n = 0;
    cin >> n;

    while(true) {
        int i = 0, j = 0, t = 0;
        cin >> i >> j >> t;
        if(i == 0 && j == 0 && t == 0) break;
        else arc[i][j] = t;
    }

    _rep_le(k, 2, n + n) {
        _rep_le(x1, 1, min(n, k - 1)) {
            _rep_le(x2, 1, min(n, k - 1)) {
                if(x1 == x2) continue;
                if((k - x1 > n) || (k - x2 > n)) continue;
                int temp = arc[x1][k - x1] + arc[x2][k - x2];
                f[k][x1][x2] = MAX(f[k-1][x1][x2], f[k-1][x1-1][x2], 
                                    f[k-1][x1][x2-1], f[k-1][x1-1][x2-1]) + temp;
            }
        }
    }

    int res = MAX(f[2*n-1][n][n], f[2*n-1][n-1][n], 
                f[2*n-1][n][n-1], f[2*n-1][n-1][n-1]) 
                + arc[n][n] + arc[1][1];
    cout << res << endl;
    return 0;
}