uva 1025——A Spy in the Metro

「爱情、让人受尽委屈。」 2022-08-17 15:24 158阅读 0赞

题意:有一个线性的车站(1-n),两个方向的车,给出列车的出发时刻和到下一站的时间,要求在到达n前换乘的等待时间最短。

思路:dp,每次有3种决策,要么等一分钟,要么往左走,要么往右,在3种决策下找到最优的然后转移。

code:

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define cls(v,c) memset(v,c,sizeof(v))
  4. #define ft(i,s,t) for (int i=s;i<=t;i++)
  5. #define frt(i,t,s) for (int i=t;i>=s;i--)
  6. const int N=205;
  7. const int INF=0x3f3f3f3f;
  8. int dp[N][N],v[N];
  9. int train[N][N][2];
  10. int main()
  11. {
  12. int n,T,m1,d,m2,ca=1;
  13. while (~scanf("%d",&n)&&n)
  14. {
  15. scanf("%d",&T);
  16. for (int i=1;i<n;i++)
  17. scanf("%d",&v[i]);
  18. cls(train,0);
  19. scanf("%d",&m1);
  20. while (m1--)
  21. {
  22. scanf("%d",&d);
  23. ft(i,1,n-1)
  24. {
  25. if (d<=T) train[d][i][0]=1;
  26. d+=v[i];
  27. }
  28. }
  29. scanf("%d",&m1);
  30. while (m1--)
  31. {
  32. scanf("%d",&d);
  33. frt(i,n-1,1)
  34. {
  35. if (d<=T) train[d][i+1][1]=1;
  36. d+=v[i];
  37. }
  38. }
  39. ft(i,1,n-1) dp[T][i]=INF;
  40. dp[T][n]=0;
  41. frt(i,T-1,0) ft(j,1,n)
  42. {
  43. dp[i][j]=dp[i+1][j]+1; //等一分钟
  44. if (j<n&&train[i][j][0]&&i+v[j]<=T)
  45. dp[i][j]=min(dp[i][j],dp[i+v[j]][j+1]); //左走
  46. if (j>1&&train[i][j][1]&&i+v[j-1]<=T)
  47. dp[i][j]=min(dp[i][j],dp[i+v[j-1]][j-1]); //右走
  48. }
  49. printf("Case Number %d: ",ca++);
  50. if (dp[0][1]>=INF) puts("impossible");
  51. else printf("%d\n",dp[0][1]);
  52. }
  53. }

发表评论

表情:
评论列表 (有 0 条评论,158人围观)

还没有评论,来说两句吧...

相关阅读

    相关 UVa1025

    题意: 某城市的地铁是线性的,有n(2≤n≤50)个车站,从左到右编号为1~n。有M1辆列车从第1站开始往右开,还有M2辆列车从第n站开始往左开。在时刻0,Mario从第1站