【题目链接】:

【题意】

有n个站台;(线性的);

每相邻两个站台之间的火车的行驶时间是固定的;

然后每天在第一个站台会向第n个站台的方向发出m1辆车;

最后一个站台会向第1个站台的方向发出m2辆车;

给出m1辆车是何时发出的,m2辆车是何时发出的(递增顺序给出);

然后有一个人要从1号站台,到n号站台;

且要求在T时刻会面;

可以在站台上等待;

问你它最少需要在站台上等待的时间;(在车上就不占时间);

【题解】

设dp[i][j]表示在第i时刻,在第j个站台所需的最短等待时间;

dp[0][1] = 0,dp[0][2..n]=INF;

在每一个站台有3种可能的决策

1.站在站台不动,时间递增1,站台不变;

2.搭上某一辆车;(向左或向右),时间不变,站台改变;

则有

dp[i][j]=dp[i−1][j]+1;

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

(如果在i−t[j]时刻,j+1站台有向左的车);

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

(如果在i−t[j]时刻,j−1站台有向右的车);

在何时在某一站有向左/向右的车可以在读时间的时候就预处理出来;

注意超过T就结束->注意break和continue;

这样DP数组的第一维最大为T,第二维最大为N

最后输出dp[T][n];

当然要判断一下是否有解

【Number Of WA】

3

【反思】

在break和continue的使用上竟然还会出现问题。

Case那个东西要记得输出。

【完整代码】

#include 
     
      using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define ms(x,y) memset(x,y,sizeof x)#define Open() freopen("F:\\rush.txt","r",stdin)#define Close() ios::sync_with_stdio(0)typedef pair
      
        pii;typedef pair
       
         pll;const int dx[9] = {
    0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {
    0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int N = 50;const int MAXT = 200;const int INF = 0x3f3f3f3f;int n,T,t[N+10],has[200+10][N+10][2];int m,dp[MAXT+10][N+10];int main(){    //Open();    //Close();    int kk = 0;    while (~scanf("%d",&n)){        if (n==0) break;        kk++;        ms(has,0),ms(dp,INF);        scanf("%d",&T);        rep1(i,1,n-1)            scanf("%d",&t[i]);        scanf("%d",&m);        rep1(i,1,m){            int now;scanf("%d",&now);            if (now>T) continue;            has[now][1][0] = 1;            rep1(j,1,n-1){                now+=t[j];                if (now>T) break;                has[now][j+1][0] = 1;            }        }        scanf("%d",&m);        rep1(i,1,m){            int now;scanf("%d",&now);            if (now>T) continue;            has[now][n][1] = 1;            rep2(j,n-1,1){                now+=t[j];                if (now>T) break;                has[now][j][1] = 1;            }        }        dp[0][1] = 0;        rep1(i,2,n) dp[0][i] = INF;        rep1(i,1,T)            rep1(j,1,n){                dp[i][j] = dp[i-1][j] + 1;                if (j+1<=n && i-t[j]>=0 && has[i-t[j]][j+1][1]) // <-                    dp[i][j] = min(dp[i][j],dp[i-t[j]][j+1]);                if (j-1>=1 && i-t[j-1]>=0 && has[i-t[j-1]][j-1][0]) // ->                    dp[i][j] = min(dp[i][j],dp[i-t[j-1]][j-1]);            }        cout << "Case Number "<
        
         <<": ";        if (dp[T][n]>=INF)            cout <<"impossible"<