题目地址：点击打开链接
题意 某城市的地铁有n个车站 编号1到n 有m1辆车向右开 给出m1个从车站1出发的时间 m2辆车向左开 给出m2个从车站n出发的时间 t[i]为火车从第i个车站开到第i+1（或相反）个车站需要的时间 Maria在车站1 她需要恰在时刻T到达第n个车站 求她的最小总车站等待时间
思路：
dp[i][j]记录的是i时间时在第j个车站到终点需要等待的最少时间。
有三种情况：
1.在车站等一秒
2.有向左的车，坐向左的车
3.有向右的车，坐向右的车
代码：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn = 55; const int maxm = 305; const int INF = 0x3f3f3f3f; int t[maxn], dp[maxm][maxn], n, T; bool hasL[maxm][maxn], hasR[maxm][maxn]; int main(void) { int ca = 1; while(cin >> n, n) { memset(t, 0, sizeof(t)); memset(dp, INF, sizeof(dp)); memset(hasL, 0, sizeof(hasL)); memset(hasR, 0, sizeof(hasR)); scanf("%d", &T); for(int i = 1; i < n; i++) scanf("%d", &t[i]); int m, x; scanf("%d", &m); for(int i = 1; i <= m; i++) { scanf("%d", &x); for(int j = 1; j <= n; j++) hasR[x][j] = 1, x += t[j]; } scanf("%d", &m); for(int i = 1; i <= m; i++) { scanf("%d", &x); for(int j = n; j >= 1; j--) hasL[x][j] = 1, x += t[j-1]; } 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(hasL[i][j]) dp[i][j] = min(dp[i][j], dp[i+t[j-1]][j-1]); if(hasR[i][j]) dp[i][j] = min(dp[i][j], dp[i+t[j]][j+1]); } } if(dp[0][1] > T) printf("Case Number %d: impossible\n", ca++); else printf("Case Number %d: %d\n", ca++, dp[0][1]); } return 0; }
