本文主要是介绍洛谷-P2196，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
int point[32], d[32][32] = { 0 }, dp[32] = {0},n, ret = -1,a = 0;
vector<int> road[32];int main()
{cin >> n;for (int i = 1; i <= n; ++i)cin >> point[i];//是有向图 i 只会指向 i+1 到 n 的节点for (int i = 1; i < n; ++i)for (int j = i + 1; j <= n; ++j) {cin >> d[i][j];}int index = 0;for (int i = n; i >= 1; --i){dp[i] = point[i];index = 0;for (int j = i + 1; j <= n; ++j) {if (d[i][j]) {if (dp[j] + point[i] > dp[i]) {dp[i] = dp[j] + point[i];index = j;}}}if (dp[i] > ret) { a = i; ret = dp[i]; }road[i].push_back(i);if (index) road[i].insert(road[i].end(), road[index].begin(), road[index].end());}for (int i = 0; i < road[a].size(); ++i)cout << road[a][i] << " ";cout << endl << ret <<endl;return 0;
}
这篇关于洛谷-P2196的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
