题目大意样例 inputoutput解释 思路代码Hit

题目大意

传送门 输入数据：

int n;//车站数 int T;//到T时刻到车站n int t[Train_Num];//车站i到i+1之间的行驶时间 int M1;//第一站向右开的列车的数目 int d1[Train_Num];//M1个列车开的时间 int M2;//第n站向左开的列车的数目 int d2[Train_Num];//M2个列车开的时间

间谍0时刻在站台1，要在T时刻到达站台n，间谍可以在车站内等车来，尽量让等的时间总和最少，求等的时间总和。

样例

input

4 55 5 10 15 4 0 5 10 20 4 0 5 10 15

4 18 1 2 3 5 0 3 6 10 12 6 0 3 5 7 12 15

2 30 20 1 20 7 1 3 5 7 11 13 17

0

output

Case Number 1: 5 Case Number 2: 0 Case Number 3: impossible

解释

用dp[i][j]表示i时刻在j站台要等的时间。 那么dp[55][4] = 0 dp[50][4] = 5 dp[35][3] = 5 dp[25][2] = 5 dp[15][3] = 5 dp[5][2] = 5 dp[0][1] = 5

思路

在一个站台一共有三种策略：

等一个时刻如果有开往左边的车，坐上开往左边的车 如果有开往右边的车，坐上开往右边的车

代码

/** * > Author: whpointz * > Mail: 506273980@qq.com * > Github: https://www.github.com/whpointz * > Description: * * > Created Time: 2017/08/05 16:38:09 **/ #include <stdio.h> #include <cstring> #define Train_Num 55 #define Time_Num 205 #define INF 1000 #define max(a,b) (a>b)? a:b //注意括号 #define min(a,b) (a>b)? b:a int n;//车站数 int T;//到T时刻到车站n int t[Train_Num];//车站i到i+1的行驶时间 int M1;//第一站向右开的列车的数目 int d1[Train_Num];//M1个列车开的时间 int M2;//第n站向左看的列车的数目 int d2[Train_Num];//M2个列车开的时间 int dp[Time_Num][Train_Num];//i时刻在车站j 最少需要等待的时间 int has_train[Time_Num][Train_Num][2];//i时刻在车站T，向右是否有车，向左是否有车 int main(){ int kase = 1; while (scanf("%d", &n) && n != 0){ //input scanf("%d", &T); for (int i = 1; i < n; i++) scanf("%d", &t[i]); scanf("%d", &M1); for (int i = 1; i <= M1; i++) scanf("%d", &d1[i]); scanf("%d", &M2); for (int i = 1; i <= M2; i++) scanf("%d", &d2[i]); //init dp[T][n] = 0;//初始状态 T时刻在车站n 需要等待的时间为0 memset(has_train, 0, sizeof(has_train)); //right for (int i = 1; i <= M1; i++) { int T_sum = d1[i]; for (int j = 1; j < n; j++){ has_train[T_sum][j][0] = 1; T_sum += t[j]; } } //left for (int i = 1; i <= M2; i++) { int T_sum = d2[i]; for (int j = n; j > 1; j--){ has_train[T_sum][j][1] = 1; T_sum += t[j-1]; } } for (int i = 1; i < n; i++) dp[T][i] = INF; 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 + t[j] <= T)//向右 i时刻j车站有车,i+t[j]<T 剪枝 dp[i][j] = min(dp[i][j], dp[i + t[j]][j + 1]); if (j > 1 && has_train[i][j][1] && i + t[j-1] <= T)//向左 i时刻j车站有车,i+t[j-1]<T 剪枝 dp[i][j] = min(dp[i][j], dp[i + t[j-1]][j - 1]); //printf("%d %d %d\n", i, j, dp[i][j]); } } printf("Case Number %d: ", kase++); if (dp[0][1] >= INF) printf("impossible\n"); else printf("%d\n",dp[0][1]); } }

Hit

has_train数组记录的时候，计算向左和向右是不一样的，我的方法中向左的车，j要减一。