本文主要是介绍hdu 4571 Travel in time(Floyd+记忆化)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：hdu 4571 Travel in time
题目大意：n个城市，m条路，总时间t，起始城市s，终点城市e，接下来给出各个城市的浏览时间，各个城市浏览后的满意程度。然后是m条路的信息。要求一个浏览顺序，使得总的满意程度最大，然后经过一个城市可以选择不去浏览，当前浏览城市的满意度一定要比前一个浏览城市的满意度高，并且最终要回到城市e
解题思路：因为经过一个城市可以不浏览，所以先用Floyd处理一下各个城市之间的最短路径，题目有个坑点就是说两个城市间不至一条边，要选最短的边移动。
接着dfs+记忆化，dp[i][j][k]表示在第i个城市，前一个城市的满意度为j，还剩下k的时间。
剪枝，当剩余时间不足以从i城市移动到e城市时，return -INF，这里不可以是0，0表示的是可以到达。
#include <stdio.h>
#include <string.h>
#include <algorithm>using namespace std;
const int N = 105;
const int INF = 0x3f3f3f3f;int n, m, T, s, e;
int tc[N], vc[N], g[N][N];
int dp[N][N][3*N];void Floyd () {for (int i = 0; i < n; i++)g[i][i] = 0;for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++)g[i][j] = min (g[i][j], g[i][k] + g[k][j]);}}
}void init () {memset(dp, -1, sizeof(dp));memset(g, INF, sizeof(g));scanf("%d%d%d%d%d", &n, &m, &T, &s, &e);for (int i = 0; i < n; i++)scanf("%d", &tc[i]);for (int i = 0; i < n; i++)scanf("%d", &vc[i]);int a, b, v;for (int i = 0; i < m; i++) {scanf("%d%d%d", &a, &b, &v);g[a][b] = g[b][a] = min(g[a][b], v);}Floyd ();
}int dfs (int u, int val, int t) {if (g[u][e] > t) return -INF;if (dp[u][val][t] != -1) return dp[u][val][t];int& ans = dp[u][val][t];ans = 0;for (int i = 0; i < n; i++) {if (vc[i] <= val) continue;ans = max(ans, dfs(i, vc[i], t - tc[i] - g[u][i]) + vc[i]);}return ans;
}int main () {int cas;scanf("%d", &cas);for (int i = 1; i <= cas; i++) {init ();printf("Case #%d:\n%d\n", i, dfs (s, 0, T));}return 0;
}这篇关于hdu 4571 Travel in time(Floyd+记忆化)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
