鹿泉专业网站建设,手机百度高级搜索入口在哪里,网页图片格式,少儿美术专业网站做课件题目链接#xff1a;https://cn.vjudge.net/problem/UVA-1025
题目大意#xff1a;Mario从第1站出发#xff0c;目的是在时刻T会见车站 nnn 的一个间谍。由于在车站等待容易被抓#xff0c;所以应尽量躲在开动的火车上#xff0c;即在车站等待的时间最短#xff0c;且Ma…题目链接https://cn.vjudge.net/problem/UVA-1025
题目大意Mario从第1站出发目的是在时刻T会见车站 nnn 的一个间谍。由于在车站等待容易被抓所以应尽量躲在开动的火车上即在车站等待的时间最短且Mario十分敏捷及时两辆方向不同的列车在同一时间停靠她也能完成换乘。 输入的第1行为 n(2≤n≤50)n(2 \le n \le 50)n(2≤n≤50) 第2行为 T(0≤T≤200)T(0 \le T \le 200)T(0≤T≤200) 第3行有 n−1n-1n−1 个整数 t1,t2,…,tn−1t_1,t_2,\dots,t_{n-1}t1,t2,…,tn−1(1≤ti≤70)(1 \le t_i \le 70)(1≤ti≤70) 其中 tit_iti 表示地铁从车站 iii 到车站 i1i1i1 的行驶时间两个方向一样。第4行为 M1(1≤M1≤50)M1(1 \le M1 \le 50)M1(1≤M1≤50)即从第1站出发向右开的列车数目。第5行包含 M1M1M1 个整数 d1,d2,…,dM1(0≤di≤250,dilt;di1)d_1,d_2,\dots,d_{M1}(0 \le d_i \le 250,d_i lt; d_{i1} )d1,d2,…,dM1(0≤di≤250,didi1) 即各列车的出发时间。第6、7行描述从第 nnn 站出发向左开的列车格式同第4、5行。输出仅包含1行即最少等待时间。无解输出 impossible.
解题思路用 dp[i][j]dp[i][j]dp[i][j] 来代表第 iii 时刻在 jjj 车站的等待时间。在每一个车站Mario有三种方法1、等待1分钟 2、搭乘向左开的列车 3、搭乘向右开的列车 我们可以先假设终态为 dp[T][n]0dp[T][n]0dp[T][n]0 然后再由终态往前推始态 dp[0][1]dp[0][1]dp[0][1] 如果 dp[0][1]≥infdp[0][1] \ge infdp[0][1]≥inf则证明无法推到输出impossible否则输出 dp[0][1]dp[0][1]dp[0][1] 的值即可。
代码
#include cstdio
#include iostream
#include algorithm
#include cmath
#include cstdlib
#include cstring
#include map
#include stack
#include queue
#include vector
#include bitset
#include set
#include utility
#include sstream
#include iomanip
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int il;ir;i)
#define lep(i,l,r) for(int il;ir;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queueint,vectorint ,greaterint q;
const int maxn (int)1e5 5;
const ll mod 1e97;
int dp[1200][120];
int d1[1200][120],d2[1200][120];
int t[120];
int sum1[120],sum2[120];
int main()
{#ifndef ONLINE_JUDGEfreopen(in.txt, r, stdin);#endif//freopen(out.txt, w, stdout);ios::sync_with_stdio(0),cin.tie(0);int n,T,c0;while(scanf(%d,n)!EOF) {if(n0) break;c;ms(sum1);ms(sum2);ms(d1);ms(d2);ms(t);scanf(%d,T);rep(i,1,n-1) {scanf(%d,t[i]);sum1[i]sum1[i-1]t[i];}lep(i,n-1,1) sum2[i]sum2[i1]t[i];int m1,m2;scanf(%d,m1);int nape;rep(i,1,m1) {scanf(%d,nape);d1[nape][1]1;rep(j,1,n-1) {d1[napesum1[j]][j1]1;}}scanf(%d,m2);rep(i,1,m2) {scanf(%d,nape);d2[nape][n]1;lep(j,n-1,1) {d2[napesum2[j]][j]1;}}rep(i,1,n-1) dp[T][i]inf;dp[T][n]0;for(int iT-1;i0;i) {for(int j1;jn;j) {dp[i][j]dp[i1][j]1;if(jnd1[i][j]1it[j]T)dp[i][j]min(dp[i][j],dp[it[j]][j1]);if(j1d2[i][j]1it[j-1]T)dp[i][j]min(dp[i][j],dp[it[j-1]][j-1]);}}printf(Case Number %d: ,c);if(dp[0][1]inf) printf(impossible\n);else printf(%d\n,dp[0][1]);}return 0;
}
