UVA 1025 A Spy in the Metro DP

　　题目链接： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=245&page=show_problem&problem=3466

　　题目描述：一个间谍要从1号车站到N号车站时刻T会面，为了不被抓住，间谍需要保证最少的停留时间，有不同时刻的列车从1-N, N-1，问间谍需要停留的最少时间是多少？

　　解题思路：一开始我想的很复杂，我是从火车和车站的角度去考虑的，这样设计到的状态转移非常麻烦，所以我在想了一个小时之后看了书，由于时间是单向流逝的，所以时间可以看做是一个天然的序，影响到决策的只有当前时间和所在车站，用d(i, j)表示在时刻i, 在车站j最少需要等待多少时间，很显然d(T, N) 就是0，其他的都还不知道。在每个状态有如下三种决策

　　　　1.等一分钟

　　　　2.搭乘向左的车

　　　　3.搭乘向右的车

　　状态转移方程: d(i, j) = min(d(i, j), dp((i+t[j]), j+1)| 1<=j<=M1) // 以搭乘向右开的车为例

　　代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <cstring>
#include <iterator>
using namespace std;

int has_train[300][80][10]; // has_train(t, i, 0)在时刻t, 车站i 是否有向右的车
int dur[80][80];
int dp[300][55]; // dp(t, i)在时刻t, 在车站i最少再需等待时间
int a[80]; // 向右开的车的始发时间
int b[80]; // 向左开的车的始发时间
const int INF = 0x3fffffff;

int main() {
    int N, T, M1, M2;
    int cases = 1;
    while( ~scanf( "%d", &N ) && N ) {
        memset(dp, 0, sizeof(dp));
        memset(has_train, 0, sizeof(has_train));
        memset(dur, 0, sizeof(dur));
        
        scanf( "%d", &T );
        for( int i = 1; i <= N-1; i++ ) {
            scanf( "%d", &dur[i][i+1] );
            dur[i+1][i] = dur[i][i+1];
        }
        scanf( "%d", &M1 );
        for( int i = 1; i <= M1; i++ ) {
            scanf( "%d", &a[i] );
            has_train[a[i]][1][0] = 1;
        }
        for( int i = 1; i <= M1; i++ ) {
            for( int j = 1; j <= N-1; j++ ) {
                has_train[a[i]+dur[j][j+1]][j+1][0] = 1;
                a[i] += dur[j][j+1];
            }
        }
        scanf( "%d", &M2 );
        
        for( int i = 1; i <= M2; i++ ) {
            scanf( "%d", &b[i] );
            has_train[b[i]][N][1] = 1;
        }
        for( int i = 1; i <= M2; i++ ) {
            for( int j = N; j >= 2; j-- ) {
                has_train[b[i]+dur[j][j-1]][j-1][1] = 1;
                b[i] += dur[j][j-1];
            }
        }
        
//        for( int i = 0; i <= T; i++ ) {
//            cout << i << " ";
//            for( int j = 1; j <= N; j++ ) {
//                cout << has_train[i][j][0] << " ";
//            }
//            cout << endl;
//        }
        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+dur[j][j+1] <= T ) {
                    dp[i][j] = min( dp[i][j], dp[i+dur[j][j+1]][j+1] );
                }
                if( j > 1 && has_train[i][j][1] && i+dur[j][j-1] <= T ) {
                    dp[i][j] = min( dp[i][j], dp[i+dur[j][j-1]][j-1] );
                }
            }
        }
        
//        for( int i = 0; i <= T; i++ ) {
//            for( int j = 1; j <= N; j++ ) {
//                cout << dp[i][j] << " ";
//            }
//            cout << endl;
//        }
        printf( "Case Number %d: ", cases++ );
        if( dp[0][1] >= INF ) printf( "impossible
" );
        else printf( "%d
", dp[0][1] );
    }
    return 0;
}

View Code

　　思考：半天RE，数组改大一点儿就AC，玄学啊......看来以后设计状态的时候不能凭着感觉瞎设计，得按部就班的，根据边界条件决定各位数的意义，这是我根据这道题总结的经验。

相关推荐