题目描述

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

第一行是一个正整数n，表示有n个车站第二行是为T，表示Mario在时刻T见车站n的间谍第三行有n-1个整数t1,t2,...,tn-1,其中ti表示地铁从车站i到i+1的行驶时间第四行为M1，及从第一站出发向右开的列车数目第五行包含M1个正整数a1,a2,...,aM1，即个列车出发的时间第六行为M2，及从第一站出发向右开的列车数目第七行包含M2个正整数b1,b2,...,bM2，即个列车出发的时间。

分析

状态：$ F_{i\ j}$ 表示在$i$时刻，人处车站$ j$的最少等待时间

状态转移方程

这一道题我们分为三个决策

等1分钟
搭乘向右的车
搭乘向左的车

等待一分钟：$ F_{i\ j}=F_{i+1 \ j}+1$
向左走：$ F_{i\ j}=Min F_{i+t_j \ j+1}$
向右走：$ F_{i\ j}=Min F_{i+t_{j-1} \ j-1}$

AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 55, M = 205;

int t[N], d[N][M];

bool l[N][M], r[N][M];

int main()

{

    int n, m, ti, cur, cas = 0;

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

    {

        scanf("%d", &ti);

        memset(l, 0, sizeof(l)), memset(r, 0, sizeof(r));

        for(int i = 1; i < n; ++i) scanf("%d", &t[i]);

        scanf("%d", &m);

        for(int i = 1; i <= m; ++i)

        {

            scanf("%d", &cur);

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

                r[j][cur] = 1, cur += t[j];

        }

        scanf("%d", &m);

        for(int i = 1; i <= m; ++i)

        {

            scanf("%d", &cur);

            for(int j = n; j >= 1; --j)

                l[j][cur] = 1, cur += t[j - 1];

        }

        memset(d, 0x3f, sizeof(d));

        d[n][ti] = 0;

        for(int j = ti - 1; j >= 0; --j)

        {

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

            {

                d[i][j]= d[i][j + 1] + 1;

                if(l[i][j]) d[i][j] = min(d[i][j], d[i - 1][j + t[i - 1]]);

                if(r[i][j]) d[i][j] = min(d[i][j], d[i + 1][j + t[i]]);

            }

        }

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

        if(d[1][0] > ti) puts("impossible");

        else printf("%d\n", d[1][0]);

    }

    return 0;

}

巴特西

【Uva1025 A Spy in the Metro】动态规划

题目描述

分析

AC代码

最新文章

热门文章