UVA

https://vjudge.net/problem/UVA-1025

某城市地铁是线性的,有n（2≤n≤50）个车站,从左到右编号1~n。有M1辆列车从第1站开始往右开,还有M2辆列车从第n站开始往左开。列车在相邻站台间所需的运行时间是固定的，因为所有列车的运行速度是相同的。在时刻0,Mario从第1站出发,目的在时刻T（0≤T≤200）会见车站n的一个间谍。在车站等车时容易被抓，所以她决定尽量躲在开动的火车上,让在车站等待的时间尽量短。列车靠站停车时间忽略不计,且Mario身手敏捷,即时两辆方向不同的列车在同一时间靠站,Mario也能完成换乘。

---

can[x][t][1/0]表示在x站台t时间向右/向左是否有地铁刚好到站（也是出站）

f[t][x]表示在t时间x站台最少的等待时间

#include<iostream>
#include<cstdio>
#include<algorithm>

#define ri register int
#define u int

namespace opt {

    inline u in() {
        u x(0),f(1);
        char s=getchar();
        while(s<'0'||s>'9') {
            if(s=='-') f=-1;
            s=getchar();
        }
        while(s>='0'&&s<='9') {
            x=(x<<1)+(x<<3)+s-'0';
            s=getchar();
        }
        return x*f;
    }

}

using opt::in;

#define NN 55

#include<cstring>

namespace mainstay {

    u N,T,m1,m2,s[NN];

    u can[NN][205][2],f[205][NN];

    inline void solve() {
        for(ri cas(1);; ++cas) {
            std::memset(can,0,sizeof(can));
            std::memset(s,0,sizeof(s));
            if(!(N=in())) return;T=in();
            for(ri i(2); i<=N; ++i) s[i]=s[i-1]+in();
            m1=in();
            for(ri k(1); k<=m1; ++k) {
                u _a(in());
                for(ri i(1); i<=N; ++i) {
                    if(_a+s[i]<=T)
                    can[i][_a+s[i]][1]=1;
                }
            }
            m2=in();
            for(ri k(1); k<=m2; ++k) {
                u _a(in());
                for(ri i(1); i<=N; ++i) {
                    if(_a+s[N]-s[i]<=T)
                    can[i][_a+s[N]-s[i]][0]=1;
                }
            }
            std::memset(f,0x3f,sizeof(f));
            f[0][1]=0;
            for(ri t(1); t<=T; ++t) {
                for(ri x(1); x<=N; ++x) {
                    f[t][x]=f[t-1][x]+1;
                    if(x^1&&can[x][t][1]&&t-(s[x]-s[x-1])>=0){
                        f[t][x]=std::min(f[t][x],f[t-(s[x]-s[x-1])][x-1]);
                    }
                    if(x^N&&can[x][t][0]&&t-(s[x+1]-s[x])>=0){
                        f[t][x]=std::min(f[t][x],f[t-(s[x+1]-s[x])][x+1]);
                    }
                }
            }
            if(f[T][N]<0x3f3f3f3f) printf("Case Number %d: %d
",cas,f[T][N]);
            else printf("Case Number %d: impossible
",cas);
        }
    }

}

int main() {

    //freopen("subway.in","r",stdin);
    //freopen("subway.out","w",stdout);
    mainstay::solve();

}