A Spy in the Metro UVA - 1025(dp 三个决策)

A Spy in the Metro UVA - 1025

题意:

有一个间谍,要去n城。n个城市之间有铁路连接。

  1. 第 i i i个城市和第 i + 1 i+1 i+1个城市之间的时间是 t i t_{i} ti​
  2. 有双向的火车,从左出发的有 m 1 m_1 m1​个,从右出发的有 m 2 m_2 m2​个。
  3. 每个火车都有出发时间。

现给你一个时间T,间谍要在T时间上在n城与人接应。现在要求缩小候车时间。

思路:

  1. 时间是单向流逝的,是一个天然的“序”,影响到决策的只有当前时间和所处的车站,所以可以用dp(i,j)表示时刻i,你在车站j(编号为1~n),最少还需要等待多长时间。边界条件是d(T,n) = 0;其他d(T,i)(i不等于n)为正无穷。
  2. 有如下三个决策。
    决策1:等一分钟。
    决策2:搭乘往右开的车(如果有)
    决策3:搭乘往左开的车(如果有)

AC

#include <iostream>
#include <bits/stdc++.h>
#define For(i,x,y) for(int i=(x); i<=(y); i++)
#define fori(i,x,y) for(int i=(x); i<(y); i++)
#define rep(i,y,x) for(int i=(y); i>=(x); i--)
#define mst(x,a) memset(x,a,sizeof(x))
#define pb push_back
#define sz(a) (int)a.size()
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int>pa;
typedef pair<ll,ll>pai;
const int INF = 0x3f3f3f3f;
int dp[250][60];
bool train[250][60][2];
int n, t[60];
int main()
{
  //  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int kase = 0;
    while(scanf("%d", &n)&&n){
        int T; scanf("%d", &T);
        fori(i,1,n)scanf("%d", &t[i]);
        int m, x, k;
        mst(dp,0); mst(train,0);
        ///right
        scanf("%d", &m);
        fori(j,0,m){
            scanf("%d", &x);
            int cnt = 1;
            for(k=x; k<=T && cnt<n ; k+=t[cnt], cnt++)train[k][cnt][0] = 1;
            train[k][cnt][0] = 1;
        }
        ///left
        scanf("%d", &m);
        fori(j,0,m){
            scanf("%d", &x);
            int cnt = n;
            for(k=x; k<=T && cnt>1 ; k+=t[cnt-1], cnt--)train[k][cnt][1] = 1;
            train[k][cnt][1] = 1;
        }
        ///dp
        For(i,1,n)dp[T][i] = INF;
        dp[T][n] = 0;
        rep(i,T-1,0){
            For(j,1,n){
                dp[i][j] = dp[i+1][j] + 1;
                if(j<n && i+t[j]<=T && train[i][j][0])dp[i][j] = min(dp[i][j], dp[i+t[j]][j+1]);
                if(j>1 && i+t[j-1]<=T && train[i][j][1])dp[i][j] = min(dp[i][j], dp[i+t[j-1]][j-1]);
            }
        }
        printf("Case Number %d: ",++kase);
        if(dp[0][1]>=INF)printf("impossible\n");
        else printf("%d\n",dp[0][1]);
    }
    return 0;
}

上一篇:1141 PAT Ranking of Institutions (25 分)


下一篇:软件测试必备Linux:21天掌握Linux命令 06 tail