UVA1025 A Spy in the Metro

UVA1025 A Spy in the Metro

题目链接

刚开始接触DP题，感觉还是有一定的难度，在这里再理一遍思路。

DP的核心就是状态和状态转移方程

首先状态的确定就是找到影响当前决策的因素，本题是当前时间和所处车站两个，所以可以用d[i][j]表示i时刻在j站最少还要等待的时间。

其次是状态转移方程，取决于决策的形式，本题主要有以下三种决策： 1.在当前车站等待一分钟。 2.搭乘向右开的车。 3.搭乘向左开的车。 找出决策后即可列出相对应的状态转移方程。 1.dp[i][j]=min(dp[i][j],dp[i+1][j]+1) 2.dp[i][j]=min(dp[i][j],dp[i+t[j][j+1]) 3.dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1])

下一步要找出边界条件和计算顺序（递推法）

这两步就要结合题意来做具体的分析 本题的边界条件为T时刻到达车站n即dp[T][n]=0 计算顺序不难判断应该从后往前，这里有一个小技巧，可以根据状态转移方程，不难看出T小的值要根据T大的求出，所以应该先求T大的值。

AC代码

注意数组范围尽量开大一些，防止越界（Runtime error）

#include
#include
#include
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN = 50+10;
const int MAXM = 50+10;
const int MAXT = 300;
int n, T, t[MAXN], M1, tr[MAXM], M2, tl[MAXM];
bool has_train[MAXT][MAXN][2];
int dp[MAXT][MAXN];
bool init()
{
	cin >> n;
	if (n == 0)
		return false;
	int time;
	memset(dp, INF, sizeof(dp));
	memset(has_train, false, sizeof(has_train));
	memset(t, 0, sizeof(t));
	cin >> T;
	for (int i = 1; i > t[i];
	cin >> M1;
	time = 0;
	for (int i = 0; i > tr[i];
		time = tr[i];
		has_train[time][1][0] = true;
		for (int i = 1; i > M2;
	for (int i = 0; i > tl[i];
		time = tl[i];
		has_train[time][n][1] = true;
		for (int i = 1; i