在这里插入图片描述

UVA1025
定义：$dp[i][j]$为在第$i$时刻间谍到达第j个车站时在车站待的最短时间,$RightTrain[i][j]$表示在第$i$时刻是否有从左向右开的列车，$LeftTrain[i][j]$同理。
初始化：$dp[0][1]=0$,剩下的dp元素$=inf$
转移方程：
在第$i$时刻间谍位于第$j$个车站时有三种转移方式：

  1. 由第$i-1$时刻在第$j$个站台等待$1$个时刻
  2. 上一次在$j$站台左边的站台并且搭上从左往右开的列车到达$j$站台
  3. 上一次在$j$站台右边的站台并且搭上从右往左开的列车到达$j$站台
    1
    2
    3
    4
    5
    6
    7
    dp[i][j] = dp[i - 1][j] + 1;//对应1。
    if (RightTrain[i][j]) {//对应2.
    dp[i][j] = min(dp[i][j], dp[i - Time[j - 1]][j - 1]);
    }
    if (LeftTrain[i][j]) {//对应3.
    dp[i][j] = min(dp[i][j], dp[i - Time[j]][j + 1]);
    }
    AC代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int dp[201][51], Time[51];
    bool RightTrain[201][51], LeftTrain[201][51];
    int n, T;
    constexpr static int inf = 0x3f3f3f3f;
    bool Input() {

    	memset(LeftTrain, false, sizeof(LeftTrain));
    	memset(RightTrain, false, sizeof(RightTrain));

    	cin >> n;
    	if (!n) {
    		return false;
    	}
    	cin >> T;
    	for (int i = 1; i <= n - 1; ++i) {
    		cin >> Time[i];
    	}
    	Time[n] = 0;
    	int M;
    	cin >> M;
    	while (M--) {
    		int StartTime;
    		cin >> StartTime;
    		RightTrain[StartTime][1] = true;
    		for (int i = 2; i <= n; ++i) {
    			StartTime += Time[i - 1];
    			if (StartTime > T) {
    				break;
    			}
    			RightTrain[StartTime][i] = true;
    		}
    	}
    	cin >> M;
    	while (M--) {
    		int StartTime;
    		cin >> StartTime;
    		LeftTrain[StartTime][n] = true;
    		for (int i = n - 1; i >= 1; --i) {
    			StartTime += Time[i];
    			if (StartTime > T) {
    				break;
    			}
    			LeftTrain[StartTime][i] = true;
    		}
    	}
    	return true;
    }
    int DP() {

    	memset(dp, 0x3f, sizeof(dp));

    	dp[0][1] = 0;
    	for (int i = 1; i <= T; ++i) {
    		for (int j = 1; j <= n; ++j) {
    			dp[i][j] = dp[i - 1][j] + 1;
    			if (RightTrain[i][j]) {
    				dp[i][j] = min(dp[i][j], dp[i - Time[j - 1]][j - 1]);
    			}
    			if (LeftTrain[i][j]) {
    				dp[i][j] = min(dp[i][j], dp[i - Time[j]][j + 1]);
    			}		
    		}
    	}
    	return dp[T][n];
    }
    int main() {
    	ios::sync_with_stdio(false);
    	int Case = 0;
    	while (Input()) {
    		int&& Ans = DP();
    		cout << "Case Number " << ++Case << ": ";
    		if (Ans >= inf) {
    			cout << "impossible" << endl;
    		}
    		else {
    			cout << Ans << endl;
    		}
    	}
    	return 0;
    }