递推DP UVA 590 Always on the run

 

题目传送门

题意：题意难懂，就是一个小偷在m天内从城市1飞到城市n最小花费，输入的是每个城市飞到其他城市的航班。

分析：dp[i][j] 表示小偷第i天在城市j的最小花费。状态转移方程：dp[i][j] = min (dp[i-1][k] + cost[k][j][t%day]) t表示在t天时k飞往j的飞机的花费

收获：

 

代码：

/************************************************ * Author :Running_Time * Created Time :2015-8-29 14:07:43 * File Name :UVA_590.cpp************************************************/#include <cstdio> #include <algorithm> #include <iostream> #include <sstream> #include <cstring> #include <cmath> #include <string> #include <vector> #include <queue> #include <deque> #include <stack> #include <list> #include <map> #include <set> #include <bitset> #include <cstdlib> #include <ctime> using namespace std;#define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 typedef long long ll; const int N = 1e5 + 10; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; int dp[1010][12]; int d[12][12]; int cost[12][12][32];int main(void) {int n, m, cas = 0;while (scanf ("%d%d", &n, &m) == 2) {if (n == 0 && m == 0) break;for (int i=1; i<=n; ++i) {for (int j=1; j<=n; ++j) {if (i != j) {scanf ("%d", &d[i][j]);for (int k=0; k<d[i][j]; ++k) {scanf ("%d", &cost[i][j][k]);}}}}memset (dp, INF, sizeof (dp));for (int i=2; i<=n; ++i) {if (cost[1][i][0]) {dp[0][i] = cost[1][i][0];}}for (int i=1; i<m; ++i) {for (int k=1; k<=n; ++k) {for (int j=1; j<=n; ++j) {if (j != k) {int c = cost[j][k][i%d[j][k]];if (c) dp[i][k] = min (dp[i][k], dp[i-1][j] + c);}}}}int ans = dp[m-1][n];printf("Scenario #%d\n", ++cas);if(ans != INF){ printf("The best flight costs %d.\n\n", ans); }else{ puts("No flight possible.\n"); } }return 0; }

　　

转载于:https://www.cnblogs.com/Running-Time/p/4773806.html

总结

以上是生活随笔为你收集整理的递推DP UVA 590 Always on the run的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。