本文主要是介绍hdu 4517 floyd+记忆化搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
有n（100）个景点，m（1000）条路，时间限制为t（300），起点s，终点e。
访问每个景点需要时间cost_i，每个景点的访问价值为value_i。
点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。
走到一个点时可以选择访问或者不访问，并且当前点的访问价值应该严格大于前一个访问的点。
现在求，从起点出发，到达终点，在时间限制内，能得到的最大价值为多少。
如果不能从s到达e，则输出0。
解析：
首先应该走到一个点可以选择访问或者不访问，所以可以用floyd求出点与点之间最近的距离为多少。
然后dp[ i ] [ j ] [ k ] 表示的是，当前走到 i 点，前一个点的价值为 j ，并且还有剩余时间 k 的最大价值。
详见代码。
代码：
#pragma comment(linker, "/STACK:1677721600")
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include <algorithm>
#define pb push_back
#define mp make_pair
#define LL long long
#define lson lo,mi,rt<<1
#define rson mi+1,hi,rt<<1|1
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define FIN freopen("in.txt", "r", stdin)
#define FOUT freopen("out.txt", "w", stdout)
#define rep(i,a,b) for(int i=(a); i<=(b); i++)
#define dec(i,a,b) for(int i=(a); i>=(b); i--)using namespace std;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double ee = exp(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = 100 + 10;
const int maxt = 300 + 10;
const double pi = acos(-1.0);
const LL iinf = 0x3f3f3f3f3f3f3f3f;int readT()
{char c;int ret = 0,flg = 0;while(c = getchar(), (c < '0' || c > '9') && c != '-');if(c == '-') flg = 1;else ret = c ^ 48;while( c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c ^ 48);return flg ? - ret : ret;
}int n, m, t, s, e;
int g[maxn][maxn];
int dp[maxn][maxn][maxt];
int cost[maxn];
int value[maxn];void floyd()
{rep(i, 0, n - 1){g[i][i] = 0;}rep(k, 0, n - 1){rep(i, 0, n - 1){rep(j, 0, n - 1){g[i][j] = Min(g[i][j], g[i][k] + g[k][j]);}}}
}int dfs(int u, int preVal, int timeLeft)
{if (g[u][e] > timeLeft)return -inf;int& res = dp[u][preVal][timeLeft];if (res != -1)return res;res = 0;rep(i, 0, n - 1){if (preVal < value[i]){res = Max(res, dfs(i, value[i], timeLeft - g[u][i] - cost[i]) + value[i]);}}return res;
}int main()
{
#ifdef LOCALFIN;
#endif // LOCALint ncase = readT();int ca = 1;while (ncase--){scanf("%d%d%d%d%d", &n, &m, &t, &s, &e);mem(dp, -1);mem(g, inf);rep(i, 0, n - 1){cost[i] = readT();}rep(i, 0, n - 1){value[i] = readT();}rep(i, 0, m - 1){int u = readT();int v = readT();int w = readT();g[u][v] = g[v][u] = Min(g[u][v], w);}floyd();int ans = dfs(s, 0, t);printf("Case #%d:\n", ca++);printf("%d\n", ans == -inf ? 0 : ans);}return 0;
}
这篇关于hdu 4517 floyd+记忆化搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
