题目大意：有N个车站，M1辆火车从车站1开到车站n，，M2辆火车从车站n开到车站1 现在有一个间谍从车站1出发，要求在T时刻的时候和火车站n的另外一名间谍见面 为了不引起怀疑，这个间谍必须将等车时间降到最小 问这个间谍从车站1出发，在T时刻去车站n见另一个间谍的等车时间的最小值
解题思路：这题有两个状态，一个是时间，另一个就是车站了，所以我们设dp[i][j]为在i时刻，j车站的等车时间的最小值 那么就有三种情况了 1.继续等1分钟 2.搭乘往右开的车(如果有) 3.搭乘往左开的车(如果有)
因为要搭车，所以我们要预先处理一下哪个车站哪一时刻有车要开，所以设一个数组has_tarin[i][j][k],表示i时刻，j车站，k方向是否有车要开动，这样就可以得到转移方程了 dp[i][j] = min(dp[i+1][j] + 1, dp[ i+t[j] ][j + 1], dp[i + t[j-1] ][j – 1]) 后面两种情况要判断
;const int M = 210;const int N = 60;const int INF = 0x3f3f3f3f;int n, T, M1, M2, t[N], d[N], e[N];int dp[M][N], cas = 1;bool has_train[M][N][2];void init() {scanf(“%d”, &T);for(int i = 1; i <= n – 1; i++)scanf(“%d”, &t[i]);scanf(“%d”, &M1);for(int i = 1; i <= M1; i++)scanf(“%d”, &d[i]);scanf(“%d”, &M2);for(int i = 1; i <= M2; i++)scanf(“%d”, &e[i]);memset(has_train, 0, sizeof(has_train));for(int i = 1; i <= M1; i++) {int tmp = d[i];has_train[tmp][1][0] = true;for(int j = 1; j <= n – 1; j++) {tmp += t[j];if(tmp > T)break;has_train[tmp][j+1][0] = true;}}for(int i = 1; i <= M2; i++) {int tmp = e[i];has_train[tmp][n][1] = true;for(int j = n – 1; j >= 1; j–) {tmp += t[j];if(tmp > T)break;has_train[tmp][j][1] = true;}}}void solve() {for(int i = 1; i <= n – 1; i++)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 && has_train[i][j][0] && i + t[j] <= T)dp[i][j] = min(dp[i][j], dp[i+t[j]][j+1]);if(j > 1 && has_train[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: “, cas++);if(dp[0][1] >= INF)printf(“impossible\n”);elseprintf(“%d\n”, dp[0][1]);}int main() {while(scanf(“%d”, &n) != EOF && n) {init();solve();}return 0;}
只要有信心，人永远不会挫败
