https://vjudge.net/problem/UVA-1025
题意：一个间谍要从第一个车站到第n个车站去会见另一个，在是期间有n个车站，有来回的车站，让你在时间T内时到达n，并且等车时间最短，输出最短等车时间。
思路：先用一个has_train[t][i][0]来表示在t时刻，在车站i，是否有往右开的车。同理，has_train[t][i][1]用来保存是否有往左开的车。
用d(i,j)表示时刻i，你在车站j，最少还需要等待多长时间。边界条件是d(T,n)=0，其他d(T,i)为正无穷。
每次有三种决策:
①：等一分钟。
②：搭成往右开的车（如果有）。
③：搭成往左开的车（如果有）。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std; const int INF = 0x3f3f3f3f; int T, n, dp[][], m1, m2, has_train[][][],t[]; int main()
{
//freopen("D:\\txt.txt", "r", stdin);
int kase = ;
while (cin >> n && n)
{
cin >> T;
for (int i = ; i < n; i++)
{
cin >> t[i];
}
memset(has_train, , sizeof(has_train));
int x;
cin >> m1;
for (int i = ; i < m1; i++)
{
cin >> x;
for (int j = ; x<=T && j <= n; j++)
{
has_train[x][j][] = ;
x += t[j];
}
} cin >> m2;
for (int i = ; i < m2; i++)
{
cin >> x;
for (int j = n; x <=T && j >; j--)
{
has_train[x][j][] = ;
x += t[j-];
}
} for (int i = ; i <= n - ; i++) dp[T][i] = INF;
dp[T][n] = ;
for (int i = T - ; i >= ; i--)
{
for (int j = ; j <= n; j++)
{
dp[i][j] = dp[i + ][j] + ; //等待一个单位
if (j < n && has_train[i][j][] && i + t[j] <= T)
dp[i][j] = min(dp[i][j], dp[i + t[j]][j + ]); //往右
if (j> && has_train[i][j][] && i + t[j - ] <= T)
dp[i][j] = min(dp[i][j], dp[i + t[j - ]][j - ]); //往左
}
}
cout << "Case Number " << ++kase << ": ";
if (dp[][] >= INF) cout << "impossible" << endl;
else cout << dp[][] << endl;
}
return ;
}