A Spy in the Metro UVA

A Spy in the Metro UVA - 1025(DP)

2024-02-17 22:48

文章标签 dp uva spy metro 1025

本文主要是介绍A Spy in the Metro UVA - 1025(DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

动态规划问题最重要的是列写状态转移方程，列写状态转移方程的时候要明白做决策的真正含义。
间谍在一个车站有三个选择，继续停留在这，等上一分钟，如果有车经过是上开往右向的车还是坐上开往左向的车。这就体现了决策的过程。接下来就是找状态，这里的状态无非就是位置+时间。用一个二维数组dp[i][j]表示时间是i在j站点，还要最少等这么多的时间。
状态转移方程：
dp[i][j] = min{dp[i+1][j] + 1, dp[i + 走到j左边站点要的时间][j-1], dp[i + 走到j右边站需要的时间] } ps：最后两项只有当有车的时候才能加上。这里就用一个数组has_train[t][i][0/1]表示在t时刻i站点是否有开向左/右的车。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int INF = 0x3f3f3f3f;int n, T, M1, M2;
int dp[220][60];   // dp[i][j]表示第i时刻在车站j，最少还需等的时间
bool has_train[220][60][2];     // has_train[t][i][0]表示t时刻在车站i是否有往右开的火车。1是向左开的车。
int cost[60];      // cost[i]表示车站 i 到 i+1 的时间损失void init() {memset(dp, 0, sizeof(dp));for(int i = 1; i <= n - 1; i++) { //表示如果没到站点n时间已经到了T永远也不会到n了，所以时间设为正无穷～dp[T][i] = INF;}dp[T][n] = 0;memset(has_train, false, sizeof(has_train));memset(cost, 0, sizeof(cost));
}int main() {freopen("input.txt", "r", stdin);int kase = 0;while(scanf("%d", &n) && n) {scanf("%d", &T);init();for(int i = 1; i < n; i++) {scanf("%d", &cost[i]);}scanf("%d", &M1);int st;for(int i = 0; i < M1; i++) {scanf("%d", &st);for(int j = 1; j <= n; j++) {has_train[st][j][0] = true;st += cost[j];}}scanf("%d", &M2);for(int i = 0; i < M2; i++) {scanf("%d", &st);for(int j = n; j >= 1; j--) {has_train[st][j][1] = true;st += cost[j-1];}}for(int i = T - 1; i >= 0; i--) {for(int j = 1; j <= n; j++) {dp[i][j] = dp[i+1][j] + 1;  //等待一个单位if (j < n && has_train[i][j][0] && i + cost[j] <= T)dp[i][j] = min(dp[i][j], dp[i + cost[j]][j + 1]);if (j > 1 && has_train[i][j][1] && i + cost[j - 1] <= T)dp[i][j] = min(dp[i][j], dp[i + cost[j-1]][j-1]);}}printf("Case Number %d: ", ++kase);if (dp[0][1] >= INF) printf("impossible\n");else printf("%d\n", dp[0][1]);}return 0;
}