uva 1025

자피서는 오리지널이 아니다.
한 도시의 지하철은 선형으로 n개의 역이 왼쪽에서 오른쪽으로 번호가 1-n이고 M1대의 지하철이 첫 번째 역에서 출발하고 M2대의 지하철이 마지막 역에서 출발하며 마리오는 첫 번째 역에서 출발한다. 그 목적은 시시각각 T역에서 n의 친구(스파이)를 만나는 것이다.역에서 차를 기다리면 잡히기 쉬우므로 가능한 한 역에서 시간을 짧게 하고 마리오는 방향이 다른 지하철의 환승을 완성할 수 있다
dp[i][j]는 i시간에 j역이 최소한 얼마나 기다려야 하는지를 나타낸다. 경계 dp[T][n]=0;기타 dp[T][i]는 무한정
세 가지 결정이 있다
1.1분 기다리기
2. 좌측 열차에 탑승
3. 오른쪽으로 달리는 차에 탑승

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <stack>

#include <cctype>

#include <string>

#include <queue>

#include <map>

#include <set>



using namespace std;



const int INF = 0xffffff;

const double ESP = 10e-8;

const double Pi = 4 * atan(1.0);

const int MAXN =  200 + 10;

const long long mod =  1000000007;

const int dr[] = {1,0,-1,0,-1,1,-1,1};

const int dc[] = {0,1,0,-1,1,-1,-1,1};

typedef long long LL;



LL gac(LL a,LL b){

    return b?gac(b,a%b):a;

}



int dp[210][MAXN];

int n,T;

int t[MAXN];

int M1,M2;

int d[MAXN];

int e[MAXN];

bool has_train[210][MAXN][2];



int main(){

#ifndef ONLINE_JUDGE

    freopen("input.in","r",stdin);

   // freopen("output.txt","w",stdout);

#endif

    int cas = 1;

    while(~scanf("%d",&n) && n){

    scanf("%d",&T);

    for(int i = 2;i <= n;i++){

        scanf("%d",&t[i]);

    }

    t[1] = 0;

    t[n+1] = 0;

    memset(has_train,0,sizeof(has_train));

    scanf("%d",&M1);

    for(int i = 1;i <= M1;i++){

        scanf("%d",&d[i]);

        int sum = d[i];

        for(int j = 1;j <= n;j++){

            sum += t[j];

            has_train[sum][j][0] = 1;

        }

    }

    scanf("%d",&M2);

    for(int i = 1;i <= M2;i++){

        scanf("%d",&e[i]);

        int sum = e[i];

        for(int j = n;j > 0;j--){

            sum += t[j+1];

            has_train[sum][j][1] = 1;

        }

    }

    for(int i = 1;i < n;i++){

        dp[T][i] = INF;

    }

    dp[T][n] = 0;

    for(int i = T-1;i > -1;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+1] <= T){ //            

                dp[i][j] = min(dp[i][j],dp[i+ t[j+1]][j+1]);

            }

            if(j > 1 && has_train[i][j][1] && i + t[j] <= T){//           

                dp[i][j] = min(dp[i][j],dp[i+t[j] ][j-1]);

            }

        }

    }

    printf("Case Number %d: ",cas++);

    if(dp[0][1] >= INF){

        printf("impossible
");

    }

    else{

        printf("%d
",dp[0][1]);

    }

    }

    return 0;

}