解题思想

这题思想很直接，定义一个表示当前点作为起点所计算的最大值的数组，递归搜每一个阶段的最大值，最后逆序返回就完了。下面就说说想这道题遇到的坑emmmm

1. 本来想的是每个点搜索之前都清空一遍dp数组重新搜每一个点，最后取最大值。但参考了下标程发现其实完全没必要重新搜......对于每次搜索都实际上是逆序搜的，当前阶段取上一阶段的最大值，直至取到路径的最后一个点（也就是值为本身的那个点），不存在上一阶段的值“非最大”的情况。因此只要是搜过的点就已经是最优值，就没有必要重新搜。

蒟蒻代码

蒟蒻的操作通常都比较迷，勿喷hhhhh

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

#define INF 2e9
#define ll long long
//
using namespace std;
const int maxn = 20 + 10;
int n;
int ans = 0;
int dl[maxn];
int tot = 0, ver[maxn * 2], nexts[maxn * 2], head[maxn];
int d[maxn], route[maxn];//dp(i) 从i出发能获得的最大数量

void add(int x, int y) {
    ver[++tot] = y;
    nexts[tot] = head[x], head[x] = tot;
}

int dp(int u) {//遍历第u个出发点
    if (d[u]) return d[u];
    int curmax = 0, foot = -1;
    for (int i = head[u]; i; i = nexts[i]) {
        int y = ver[i];//下一个节点编号为y
        if (d[y] == 0) d[y] = dp(y);
        if (d[y] > curmax) {
            curmax = d[y];
            foot = y;//更新下一个节点为y
        }
    }
    route[u] = foot;
    return dl[u] + curmax;//返回u点出发的最大值
}

int main() {
    int a, start = -1;
    cin >> n;
    memset(d, 0, sizeof(d));
    memset(route, -1, sizeof(route));//路径初始化为-1
    for (int i = 1; i <= n; i++) cin >> dl[i];
    for (int i = 1; i <= n; i++) {
        //输入每一个结点的对应的连接点
        for (int j = i + 1; j <= n; j++) {
            cin >> a;
            if (a) add(i, j);//1就加一条边
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!d[i]) {
            d[i] = dp(i);
            if (d[i] > ans) {
                ans = d[i];
                start = i;//找最佳开始起点编号
            }
        }
    }
    cout << start << " ";
    while (start != -1) {//输出到-1为止
        if (route[start] != -1)
            cout << route[start] << " ";
        start = route[start];
    }
    cout << endl << ans;
    return 0;
}