uva 590 - Always on the run(01双肩包)
uva 590 - Always on the run(01背包)
题目连接:590 - Always on the run
题目大意:给出n和k, 然后再给出n * ( n - 1) 行数字,第i个(n - 1)行带表城市i与另外的(n - 1) 个城市之间航班。
对于每一行来说已经确定的是哪两个城市之间的航班了,第一个数字代表航班价格的波动周期(天),后面day[i][j]个数代表对应日子的航班价格,现在求出k次航班后从城市1移动到城市n的花费最小值, 输出最小值,不能到达输出“No flight possible"。
解题思路:题目看了很久愣是没看懂,去搜了下题解,也没有将的很详细的, 所以题目大意基本是猜的。我的做法是用二维数组记录最优解,进行递推,dp[i][d]代表在第d天到达城市i的最小花费,dp[i][d] = min(dp[i][d], dp[j][d - 1][t] + val[j][i][t]) (t 为d对应周期循环的天数, j移动来的那个城市)
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <climits> const int N = 15; int min(int a, int b) { return a > b ? b : a; } int n, k; int day[N][N], val[N][N][N + 20], dp[N][1005]; void read() { memset(day, 0, sizeof(day)); memset(val, 0, sizeof(val)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i != j) { scanf("%d", &day[i][j]); for (int t = 1; t <= day[i][j]; t++) scanf("%d", &val[i][j][t]); } } } for (int i = 0; i <= n; i++) for (int t = 0; t <= k; t++) dp[i][t] = INT_MAX; } void solve() { dp[1][0] = 0; for (int d = 1; d <= k; d++) { for (int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if (i != j) { int t = (d - 1) % day[j][i] + 1; if (val[j][i][t] && dp[j][d - 1] != INT_MAX) dp[i][d] = min(dp[i][d], dp[j][d - 1] + val[j][i][t]); } } } } } int main() { int cas = 1; while (scanf("%d%d", &n, &k) && n && k) { read(); printf("Scenario #%d\n", cas++); solve(); if (dp[n][k] == INT_MAX) printf("No flight possible.\n\n"); else printf("The best flight costs %d.\n\n", dp[n][k]); } return 0; }