题目传送门

题意（拙劣的有道翻译）

特工玛丽亚被派往算法城执行一项特别危险的任务。后几个惊险的事件，我们发现她在算法的第一站城市地铁，检查时间表。算法城市地铁是由一条线路组成的，列车是双向运行的，所以它的时间表并不复杂。玛丽亚在算法城地铁的最后一站与一名当地间谍约会。玛丽亚知道一个强大的组织在追捕她。她也知道当她在车站等车的时候，她是冒着被抓住的危险。躲在跑着的火车里要安全得多，所以她决定继续跑着尽可能多的训练，即使这意味着要前后移动。玛丽亚需要知道在车站等她到最后一站的时间最少的时间表约会。你必须编写一个程序，在玛丽亚的最佳日程安排中找出总等待时间。算法城市地铁系统有N个车站，连续编号从1列火车到N列火车向两个方向移动:从第一个站到最后一个站，从最后一个站回到第一站。火车在两个连续的车站之间运行所需的时间是固定的火车以相同的速度行驶。火车在每个车站都停很短的一站，你可以忽略它为了简单起见。由于她是一个非常快的代理人，玛丽亚总是可以在一个车站换车，即使涉及到的火车在同一时间停在那个车站

分析

我们首先可以得到，第一个关键因素是时间，我们可以推出每一个时间下的每一站停靠的列车信息，然后我们的主角在每一站有三个选择：1.在车站等着。2.上车向右。3.上车向左。所以我们动态规划的信息就是时间和车站，这就是递推的两个维度，我们可以建立一个dp数组，行坐标为时间，列坐标为车站。于是我们会得到三种情况下的三个状态转移方程。
dp[i][j]=dp[i+1][j]+1
dp[i][j]=min(dp[i][j],dp[i+move[j]][j+1])
dp[i][j]=min(dp[i][j],dp[i+move[j-1]][j-1])
还有一个关键点就是我们得知道这个车站是否有向左开或者向右开的列车，所以我们就需要去构造一张是否有车的图表，可以采用下面的代码来构建

cin >> m1;
       for(int i=1;i<=m1;i++){
           cin>>d;
           for(int j=0;j<n;j++) {
               d+=move[j];
               if(d>t)
                   break;
               has_train[d][j+1][0]=1;
           }
       }
       cin >> m2;
       for(int i=0;i<m2;i++){
           cin>>d;
           for(int j=n;j>0;j--) {
               d+=move[j];
               if(d>t)
                   break;
               has_train[d][j][1]=1;
           }
       }

我们还有最后一个棘手的问题，我们该如何定义递推的dp数组的初始值呢，因为我们取最小值，所以我们要把初始值设置的足够大，当然，递推的起点自然得设置为0

代码

#include <iostream>
#include <cstring>
using namespace std;
const int N=60,T=210;
const int INF=1e8;

int has_train[T][N][2];
int dp[T][N];

int main(){
    ios::sync_with_stdio(false);
    int n,t,m1,m2,d;
    for(int cas=1;cin>>n&&n;cas++) {
        cin>>t;
        int *move = new int[n+10];
        move[0]=move[n]=0;
        for (int i = 1; i < n; i++)
            cin >> move[i];
        memset(has_train,0,sizeof(has_train));
        cin >> m1;
        for(int i=1;i<=m1;i++){
            cin>>d;
            for(int j=0;j<n;j++) {
                d+=move[j];
                if(d>t)
                    break;
                has_train[d][j+1][0]=1;
            }
        }
        cin >> m2;
        for(int i=0;i<m2;i++){
            cin>>d;
            for(int j=n;j>0;j--) {
                d+=move[j];
                if(d>t)
                    break;
                has_train[d][j][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(j<n&&has_train[i][j][0]&&i+move[j]<=t)
                    dp[i][j]=min(dp[i][j],dp[i+move[j]][j+1]);
                if(j>1&&has_train[i][j][1]&&i+move[j-1]<=t)
                    dp[i][j]=min(dp[i][j],dp[i+move[j-1]][j-1]);
            }
        }
        cout << "Case Number " << cas << ": ";
        if(dp[0][1]>=INF)
            cout << "impossible" << endl;
        else
            cout << dp[0][1] << endl;
    }
    return 0;
}

In The End

UVA1025题：城市里的间谍（动态规划）

题目传送门

题意（拙劣的有道翻译）

分析

代码