编辑代码

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 1001
int arr[MAX][MAX];
int f[MAX][MAX];
int route[MAX];

void InputArray(int n);
int GetSubArrayMax(int n);
void OutputArray(int n);
int minimumTotal(int n);
void OutputRoute(int n);
void OutputOptimalRoute(int n, int min);
void OutputArray1(int n); // 打印一维数组

int main() {
    int t, n, max;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n;
        InputArray(n);
        int min = minimumTotal(n);
        cout << min << endl;
        // OutputArray(n);
        // OutputRoute(n);
        // cout << GetLeftColumn(n);
        OutputOptimalRoute(n, min);
        cout << endl;
    }
}

void InputArray(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i + 1; j++) {
            cin >> arr[i][j];
        }
    }
}
void OutputArray(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i + 1; j++) {
            cout << f[i][j] << " ";
        }
        cout << endl;
    }
}
int minimumTotal(int n) {
    f[0][0] = arr[0][0];
    for (int i = 1; i < n; i++) {
        f[i][0] = f[i - 1][0] + arr[i][0]; // 最左侧只能从上面来 然后+当前位置的值
        for (int j = 1; j < i; j++) {
            f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + arr[i][j];
        }
        // 最右侧只能从左上方来
        f[i][i] = f[i - 1][i - 1] + arr[i][i];
    }
    int min = 1001;
    // 求最下面一行的最小值
    for (int j = 0; j < n; j++) {
        if (f[n - 1][j] < min)    min = f[n - 1][j];
    }
    
    return min;
}

void OutputRoute(int n) {
    for (int i = 0; i < n; i++) {
        if(i == 0)
            cout << minimumTotal(i + 1) << " ";
        else {
            cout << minimumTotal(i + 1) - minimumTotal(i) << " ";
        }
    }

}
void OutputArray1(int n) {
    for (int i = 0; i < n; i++) {
        cout << route[i] << " ";
    }
}
void OutputOptimalRoute(int n, int min) {
    int rowMin = min; // 往上走的过程中 f[i][j]的值
    int index = 0;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < i + 1; j++) {
            // cout << f[i][j] << " ";
            if (f[i][j] == rowMin) {
                route[index] = arr[i][j];
                rowMin = rowMin - route[index]; // 上一行位置 = 当前所处的位置的f[i][j] - 当前位置的值
                index++;
            }
        }
        // cout << endl;
    }
    // 倒序输出route
    for (int i = n - 1; i >= 0; i--) {
        if(i == 0)  cout << route[i];
        else cout << route[i] << "-->";
    }
}