题目链接：http://acm.hust.edu.cn/vjudge/problem/35913
题意：有一个间谍开始在1号点，他想在T时刻到达n号点，给出每两个站的通车时间。有m1辆车分别在di时刻离开1号点驶向n号点；有m2辆车分别在ei时刻离开n号点驶向1号点。求间谍在T时刻到达n号点时在车站停留的最短总时间。不计列车停车时间，且可以随意换乘也可以在车站停留等待。
思路：dp[t][i]表示t时刻在i号站台的停留最短总时间。一开始我们可以根据每辆车的出发时间推断出i时刻在j站台是否存在向左/右开的列车。那么对于dp[i][j]，有三种选择，坐上向左开的车，坐上向右开的车，停留一个单位时刻。
#include <cstdio> #include <cmath> #include <cstring> #include <string> #include <cstdlib> #include <iostream> #include <algorithm> #include <stack> #include <map> #include <set> #include <vector> #include <sstream> #include <queue> #include <utility> using namespace std; #define rep(i,j,k) for (int i=j;i<=k;i++) #define Rrep(i,j,k) for (int i=j;i>=k;i--) #define Clean(x,y) memset(x,y,sizeof(x)) #define LL long long #define ULL unsigned long long #define inf 0x7fffffff #define mod 100000007 bool can[300][100][2]; int dp[300][100]; int a[59]; int kase = 0; int n,T; void init() { Clean(dp,0x3f); Clean(can,false); cin>>T; rep(i,1,n-1) scanf("%d",&a[i]); int m,temp; cin>>m; rep(i,1,m) //处理向右行驶 { scanf("%d",&temp); int now = temp; can[now][1][0] = true; rep(j,1,n-1) { now += a[j]; if ( now > T ) continue; can[now][j+1][0] = true; } } cin>>m; rep(i,1,m) //处理向左行驶 { scanf("%d",&temp); int now = temp; can[now][n][1] = true; Rrep(j,n-1,1) { now += a[j]; if ( now > T ) continue; can[now][j][1] = true; } } } void solve() { dp[0][1] = 0; rep(i,1,T) //枚举时刻 { rep(j,1,n) { dp[i][j] = min( dp[i-1][j] + 1 , dp[i][j] ); //停留一个时刻 if ( i-a[j-1] >= 0 && can[i-a[j-1]][j-1][0] ) //当前状态可以由左边的站台转移过来 dp[i][j] = min( dp[i][j] , dp[i-a[j-1]][j-1] ); if ( i-a[j] >= 0 && can[i-a[j]][j+1][1] )//当前状态可以由右边的站台转移过来 dp[i][j] = min( dp[i][j] , dp[i-a[j]][j+1] ); } } printf("Case Number %d: ",++kase); if ( dp[T][n] > 1000000000 ) puts("impossible"); else printf("%d\n",dp[T][n]); } int main() { while( cin>>n ) { if(!n) break; init(); solve(); } return 0; }
