学步园

第一道动态规划。。书中给的状态转移的设计感觉很巧妙

要注意下数组大小避免RE。

Run Time: 0.032s

#define UVa  "LT9-1.1025.cpp"		//A Spy in the Metro
char fileIn[30] = UVa, fileOut[30] = UVa;

#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

//Global Variables. Reset upon Each Case!
const int maxt = 4000 + 10, maxn = 50 + 10, maxm = 50 + 10, INF = 100000000;
int N, T, M1, M2, t[maxn], d[maxm], e[maxm];
int has_train[maxt][maxn][2];
int dp[maxt][maxn];
/////

void init() {
    memset(has_train, 0, sizeof(has_train));
    scanf("%d", &T);
    for(int i = 0; i < N-1; i ++) scanf("%d", &t[i]);
    scanf("%d", &M1);
    for(int i = 0; i < M1; i ++) scanf("%d", &d[i]);
    scanf("%d", &M2);
    for(int i = 0; i < M2; i ++) scanf("%d", &e[i]);
    for(int i = 0; i < M1; i ++) {          //trains from left start point.
        int time = d[i];
        has_train[time][0][0] = 1;
        for(int j = 0; j < N-1; j ++) {     //N-1 stations, N-2 intervals.
            time += t[j];
            has_train[time][j+1][0] = 1;
        }
    }
    for(int i = 0; i < M2; i ++) {          //trains from right start point.
        int time = e[i];
        has_train[time][N-1][1] = 1;
        for(int j = N-2; j >= 0; j --) {     //N-1 stations, N-2 intervals.
            time += t[j];
            has_train[time][j][1] = 1;
        }
    }
}

int main() {
    int kase = 0;
    while(scanf("%d", &N) && N) {
        init();
        for(int i = 0; i < N; i ++) dp[T][i] = INF;
        for(int i = 0; i <= T; i ++) dp[i][N-1] = 0;

        for(int i = T - 1; i >= 0; i --) {
            for(int j = 0; j < N; j ++) {
                dp[i][j] = dp[i+1][j] + 1;
                if(has_train[i][j][0] && j < N-1 && i + t[j] <= T)
                    dp[i][j] = min(dp[i][j], dp[i+t[j]][j+1]);
                if(has_train[i][j][1] && j > 0 && i + t[j-1] <= T)
                    dp[i][j] = min(dp[i][j], dp[i+t[j-1]][j-1]);
            }
        }
        printf("Case Number %d: ", ++kase);
        if(dp[0][0] >= INF) printf("impossible\n");
        else printf("%d\n", dp[0][0]);
    }
    return 0;
}