首页 > 代码库 > UVA - 590Always on the run(递推)
UVA - 590Always on the run(递推)
题目:UVA - 590Always on the run(递推)
题目大意:有一个小偷现在在计划着逃跑的路线,但是又想省机票费。他刚开始在城市1,必须K天都在这N个城市里跑来跑去,最后一天达到城市N,问怎样计划路线的得到最少的费用。
解题思路:一开始题目意思就理解有些问题。
dp【k】【i】:代表在第k天小偷从某一个城市(除了i)坐飞机飞到城市i(到达城市i也是在这一天)。第k天的话,就看这一天坐哪个航班,加上之前的费用是最小的,就选这个方案。然后k+ 1天就又是由第k天推出来的。
状态转移方程:dp【k】【i】 = Min (dp【k - 1】【j】(i != j) + v[j][i][k]).
代码:
#include <cstdio> #include <cstring> const int N = 15; const int M = 35; const int maxn = 1005; const int INF = 0x3f3f3f3f; int n, k; int t[N][N]; int v[N][N][M]; int dp[maxn][N]; int Min (const int a, const int b) { return a < b? a: b; } int main () { int cas = 0; while (scanf ("%d%d", &n, &k), n || k) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) continue; scanf ("%d", &t[i][j]); for (int d = 0; d < t[i][j]; d++) { scanf ("%d", &v[i][j][d]); if (v[i][j][d] == 0) v[i][j][d] = INF; } } } for (int i = 1; i <= k; i++) for (int j = 1; j <= n; j++) dp[i][j] = INF; for (int i = 2; i <= n; i++) dp[1][i] = v[1][i][0]; for (int d = 2; d <= k; d++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if (i != j && dp[d - 1][j] != INF) dp[d][i] = Min (dp[d][i], dp[d - 1][j] + v[j][i][(d - 1) % t[j][i]]); } //printf ("%lld\n", INF); printf ("Scenario #%d\n", ++cas); if (dp[k][n] != INF) printf ("The best flight costs %d.\n\n", dp[k][n]); else printf ("No flight possible.\n\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。