題目鏈接：https://cn.vjudge.net/problem/UVA-1025

題目大意：Mario從第1站出發，目的是在時刻T會見車站 $n$ 的一個間諜。由于在車站等待容易被抓，所以應盡量躲在開動的火車上，即在車站等待的時間最短，且Mario十分敏捷，及時兩輛方向不同的列車在同一時間停靠，她也能完成換乘。
輸入的第1行為 $n(2\le n\le 50)$ ，第2行為 $T(0\le T\le 200)$ ，第3行有 $n?1$ 個整數 $t_1,t_2,\dots ,t_{n?1}$$(1\le t_i\le 70)$ ，其中 $t_i$ 表示地鐵從車站 $i$ 到車站 $i+1$ 的行駛時間（兩個方向一樣）。第4行為 $M1(1\le M1\le 50)$，即從第1站出發向右開的列車數目。第5行包含 $M1$ 個整數 $d_1,d_2,\dots ,d_{M1}(0\le d_i\le 250,d_i<d_{i+1})$ ，即各列車的出發時間。第6、7行描述從第 $n$ 站出發向左開的列車，格式同第4、5行。輸出僅包含1行，即最少等待時間。無解輸出 impossible.

解題思路：用 $dp[i][j]$ 來代表第 $i$ 時刻在 $j$ 車站的等待時間。在每一個車站，Mario有三種方法：1、等待1分鐘
2、搭乘向左開的列車
3、搭乘向右開的列車
我們可以先假設終態為 $dp[T][n]=0$ ，然后再由終態往前推始態 $dp[0][1]$ ，如果 $dp[0][1]\ge inf$，則證明無法推到，輸出impossible，否則輸出 $dp[0][1]$ 的值即可。

代碼：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
int dp[1200][120];
int d1[1200][120],d2[1200][120];
int t[120];
int sum1[120],sum2[120];
int main() 
{#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);ios::sync_with_stdio(0),cin.tie(0);int n,T,c=0;while(scanf("%d",&n)!=EOF) {if(n==0) break;c++;ms(sum1);ms(sum2);ms(d1);ms(d2);ms(t);scanf("%d",&T);rep(i,1,n-1) {scanf("%d",&t[i]);sum1[i]=sum1[i-1]+t[i];}lep(i,n-1,1) sum2[i]=sum2[i+1]+t[i];int m1,m2;scanf("%d",&m1);int nape;rep(i,1,m1) {scanf("%d",&nape);d1[nape][1]=1;rep(j,1,n-1) {d1[nape+sum1[j]][j+1]=1;}}scanf("%d",&m2);rep(i,1,m2) {scanf("%d",&nape);d2[nape][n]=1;lep(j,n-1,1) {d2[nape+sum2[j]][j]=1;}}rep(i,1,n-1) dp[T][i]=inf;dp[T][n]=0;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&&d1[i][j]==1&&i+t[j]<=T)dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]);if(j>1&&d2[i][j]==1&&i+t[j-1]<=T)dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]);}}printf("Case Number %d: ",c);if(dp[0][1]>=inf) printf("impossible\n");else printf("%d\n",dp[0][1]);}return 0;
}