例题9-1 UVa 1025

/* 算法竞赛入门 LRJ 例题9-1 城市里的间谍(UVa 1025) 时间: 2017/03/10 递归 预处理数组：mp[i][j][0] 代表i时刻，在j点是否有车从左边来，mp[i][j][1] 代表i时刻，在j点是否有车从左边来。 dp[i][j] 代表i时刻，在j点的最短还需等待时间。 dp[T][n] = 0; dp[i][j] = dp[i+1][j]+1; if(mp[i][j][0]) dp[i][j] = min(dp[i][j],dp[i+t[j]][j+1]); if(mp[i][j][1]) dp[i][j] = min(dp[i][j],dp[i+t[j-1]][j-1]); */ #include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <cmath> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; const int N = 55; int mp[410][N][2],dp[410][N]; int t[N],d[N],e[N]; int main() { int n,T,M1,M2,sum; int cas = 1; while(cin >> n) { if(!n) break; cin >> T; memset(mp,0,sizeof(mp)); memset(dp,0,sizeof(dp)); for(int i = 1; i < n; i++) cin >> t[i]; cin >> M1; for(int i = 1; i <= M1; i++) { cin >> d[i]; sum = d[i]; for(int j = 1; j <= n; j++) { mp[sum][j][0] = 1; if(j != n) sum += t[j]; } } cin >> M2; for(int i = 1; i <= M2; i++) { cin >> e[i]; sum = e[i]; for(int j = n-1; j >= 1; j--) { mp[sum][j+1][1] = 1; sum += t[j]; } mp[sum][1][1] = 1; } for(int i = 1; i < n; 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(mp[i][j][0] && i+t[j] <= T && j+1 <= n) dp[i][j] = min(dp[i][j],dp[i+t[j]][j+1]); if(mp[i][j][1] && i+t[j-1] <= T && j-1 >= 1) dp[i][j] = min(dp[i][j],dp[i+t[j-1]][j-1]); } } printf("Case Number %d: ",cas++); if(dp[0][1] >= INF) puts("impossible"); else printf("%d\n",dp[0][1]); } return 0; }