商业网站开发选题的目的,工商注册公司代理,游戏门户网站有哪些,淘宝网站怎么做网站题意#xff1a;有一个线性的车站#xff08;1-n#xff09;#xff0c;两个方向的车#xff0c;给出列车的出发时刻和到下一站的时间#xff0c;要求在到达n前换乘的等待时间最短。 思路#xff1a;dp#xff0c;每次有3种决策#xff0c;要么等一分钟#xff0c;要…题意有一个线性的车站1-n两个方向的车给出列车的出发时刻和到下一站的时间要求在到达n前换乘的等待时间最短。 思路dp每次有3种决策要么等一分钟要么往左走要么往右在3种决策下找到最优的然后转移。 code #include bits/stdc.h
using namespace std;#define cls(v,c) memset(v,c,sizeof(v))
#define ft(i,s,t) for (int is;it;i)
#define frt(i,t,s) for (int it;is;i--)
const int N205;
const int INF0x3f3f3f3f;
int dp[N][N],v[N];
int train[N][N][2];
int main()
{int n,T,m1,d,m2,ca1;while (~scanf(%d,n)n){scanf(%d,T);for (int i1;in;i)scanf(%d,v[i]);cls(train,0);scanf(%d,m1);while (m1--){scanf(%d,d);ft(i,1,n-1){if (dT) train[d][i][0]1;dv[i];}}scanf(%d,m1);while (m1--){scanf(%d,d);frt(i,n-1,1){if (dT) train[d][i1][1]1;dv[i];}}ft(i,1,n-1) dp[T][i]INF;dp[T][n]0;frt(i,T-1,0) ft(j,1,n){dp[i][j]dp[i1][j]1; //等一分钟if (jntrain[i][j][0]iv[j]T)dp[i][j]min(dp[i][j],dp[iv[j]][j1]); //左走if (j1train[i][j][1]iv[j-1]T)dp[i][j]min(dp[i][j],dp[iv[j-1]][j-1]); //右走}printf(Case Number %d: ,ca);if (dp[0][1]INF) puts(impossible);else printf(%d\n,dp[0][1]);}}
