HDU 1224 Free DIY Tour——DP

HDU 1224 Free DIY Tour——DP

题目虽然长，但实际上就是让你找1到n+1的一条权值最大的路径，并输出这条路径（从1到n+1,并且n+1输出时视为1）

#include #include #include #include using namespace std;int n, a[110], dp[110], graph[110][110], pre[110];void print(int x) { if (x == 1) { printf("1"); return; } print(pre[x]); printf("->%d", x);}int main(){ int T; scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { if (kase != 1) printf("\n"); memset(dp, 0, sizeof(dp)); memset(pre, 0, sizeof(pre)); memset(graph, 0, sizeof(graph)); int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } a[n + 1] = 0; int m; scanf("%d", &m); while (m--) { int a, b; scanf("%d %d", &a, &b); if (a > b) swap(a, b); graph[b][a] = 1; } for (int i = 1; i <= n + 1; i++) { for (int j = 1; j < i; j++) { if (graph[i][j] && dp[j] + a[i] > dp[i]) { dp[i] = dp[j] + a[i]; pre[i] = j; } } } printf("CASE %d#\npoints : %d\n", kase, dp[n + 1]); printf("circuit : "); print(pre[n + 1]); printf("->%d\n", 1); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。