云服务器可以做两个网站,国外建站网,一个专门做网站建设的公司,网站注册建设题目链接 https://vjudge.net/problem/UVA-1025 【题意】 某城市里的地铁是线性的#xff0c;有n个车站#xff08;2n50#xff09;#xff0c;有M1辆列车从第1站从左往右开#xff0c;有M2辆列车从第n站从右往左开#xff0c;在0时刻间谍从第一站出发有n个车站2n50有M1辆列车从第1站从左往右开有M2辆列车从第n站从右往左开在0时刻间谍从第一站出发目的是要在时刻T0T200与另一个人在第n个车站碰头在车站等车时容易被抓所以间谍要尽量躲在开动的火车上从而让他在车站的等待时间尽可能短。停车时间忽略不计并且认为间谍可以瞬间完成换乘操作。 【输入格式】 多组输入第一行为n第二行为T第三行有n-1个整数代表地铁从第i站开到第i1站所用时间两个方向上的时间是一样的第4行是M1表示第1站出发向右开的火车数目第五行有M1个整数代表每辆车的出发时间。67行同45行一样描述的是从右往左开的列车信息。 【输出格式】 有解时输出最短时间无解输出”impossible” 【思路】 把时刻和所处车站看成一种状态那么假设dp[i][j]表示在时刻i车站j间谍的最小等待时间是多少。那么接下来间谍只能有这样三种活动(1).原地等待1s等待时间1. (2)坐车往左走. (3)坐车往右走所以dp[i][j]一定是这三种情况的最小值只需要需处理出每个车站在某个时刻有没有向左开和向右开的火车之后就可以计算递推dp[i][j]了初始化dp[T][1]~dp[T][n-1]为无穷大dp[T][n]0 #includebits/stdc.h
using namespace std;const int inf 2e9;
const int maxt 220;
const int maxn 60;int n, T, cnt, kase 0;
int t[maxn];
bool hasTrain[maxt][maxn][2];
int dp[maxt][maxn];void d() {for (int i 0; i T; i) {for (int j 1; j n; j) dp[i][j] inf;}dp[T][n] 0;for (int i T - 1; i 0; --i) {for (int j 1; j n; j) {dp[i][j] min(dp[i][j], dp[i 1][j] 1);if (j 1 hasTrain[i][j][0] i t[j - 1] T) {dp[i][j] min(dp[i][j], dp[i t[j - 1]][j - 1]);}if (j n hasTrain[i][j][1] i t[j] T) {dp[i][j] min(dp[i][j], dp[i t[j]][j 1]);}}}if (dp[0][1] inf) printf(Case Number %d: impossible\n, kase);else printf(Case Number %d: %d\n, kase, dp[0][1]);
}int main() {while (scanf(%d, n) 1 n) {scanf(%d, T);for (int i 1; i n; i) scanf(%d, t[i]);memset(hasTrain, 0, sizeof(hasTrain));scanf(%d, cnt);for (int i 1; i cnt; i) {int start;scanf(%d, start);for (int j 1; j n; j) {hasTrain[start][j][1] true;//1向右start t[j];if (start T) break;}}scanf(%d, cnt);for (int i 1; i cnt; i) {int start;scanf(%d, start);for (int j n; j 1; --j) {hasTrain[start][j][0] true;//0向左start t[j - 1];if (start T) break;}}d();}return 0;
} 转载于:https://www.cnblogs.com/wafish/p/10465353.html
