https://www.luogu.org/problem/show?pid=2583
设在时刻i，车站j到结束最短需要等待f(i,j)分钟，得状态转移方程：
f(i,j)=min{
f(i+1,j)+1
f(i+t[j-1],j-1) (若时刻i有向左走的车)
f(i+t[j],j+1) (若时刻i有向右走的车)
}
因此需要预处理每一时刻有没有车可以坐。
初始值f(t,n)=0，其他均为∞。
1 #include <iostream> 2 #include <cstring> 3 #define maxt 210 4 #define maxn 60 5 #define inf 1000 6 using namespace std; 7 bool has_train[maxt][maxn][2]; 8 int dp[maxt][maxn]; 9 int n, tt, t[maxn], m1, m2, d; 10 int main() 11 { 12 int cnt = 1; 13 while (true) 14 { 15 cin >> n; 16 if (n == 0) break; 17 cin >> tt; 18 for (int i = 1; i<n; i++) cin >> t[i]; 19 20 //预处理has_train数组 21 memset(has_train, false, maxt * maxn * 2); 22 cin >> m1; 23 while (m1--) 24 { 25 cin >> d; 26 for (int j = 1; j <= n - 1 && d <= tt; j++) 27 { 28 has_train[d][j][0] = true; 29 d += t[j]; 30 } 31 } 32 cin >> m2; 33 while (m2--) 34 { 35 cin >> d; 36 for (int j = n; j >= 2 && d <= tt; j--) 37 { 38 has_train[d][j][1] = true; 39 d += t[j - 1]; 40 } 41 } 42 43 //初始化dp数组 44 for (int i = 1; i <= n; i++) 45 dp[tt][i] = inf; 46 dp[tt][n] = 0; 47 48 for (int i = tt - 1; i >= 0; i--) 49 { 50 for (int j = 1; j <= n; j++) 51 { 52 dp[i][j] = dp[i + 1][j] + 1; //+1s 53 if (i + t[j] <= tt && j + 1 <= n && has_train[i][j][0]) 54 dp[i][j] = min(dp[i][j], dp[i + t[j]][j + 1]); //向右走 55 if (i + t[j - 1] <= tt && j - 1 >= 1 && has_train[i][j][1]) 56 dp[i][j] = min(dp[i][j], dp[i + t[j - 1]][j - 1]); //向左走 57 } 58 } 59 if (dp[0][1]<inf) 60 cout << "Case Number " << cnt << ": " << dp[0][1] << endl; 61 else 62 cout << "Case Number " << cnt << ": impossible" << endl; 63 cnt++; 64 } 65 return 0; 66 }