題意：有一個(gè)線性的車站（1-n），兩個(gè)方向的車，給出列車的出發(fā)時(shí)刻和到下一站的時(shí)間，要求在到達(dá)n前換乘的等待時(shí)間最短。

思路：dp，每次有3種決策，要么等一分鐘，要么往左走，要么往右，在3種決策下找到最優(yōu)的然后轉(zhuǎn)移。

code：

#include <bits/stdc++.h> using namespace std;#define cls(v,c) memset(v,c,sizeof(v)) #define ft(i,s,t) for (int i=s;i<=t;i++) #define frt(i,t,s) for (int i=t;i>=s;i--) const int N=205; const int INF=0x3f3f3f3f; int dp[N][N],v[N]; int train[N][N][2]; int main() {int n,T,m1,d,m2,ca=1;while (~scanf("%d",&n)&&n){scanf("%d",&T);for (int i=1;i<n;i++)scanf("%d",&v[i]);cls(train,0);scanf("%d",&m1);while (m1--){scanf("%d",&d);ft(i,1,n-1){if (d<=T) train[d][i][0]=1;d+=v[i];}}scanf("%d",&m1);while (m1--){scanf("%d",&d);frt(i,n-1,1){if (d<=T) train[d][i+1][1]=1;d+=v[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[i+1][j]+1; //等一分鐘if (j<n&&train[i][j][0]&&i+v[j]<=T)dp[i][j]=min(dp[i][j],dp[i+v[j]][j+1]); //左走if (j>1&&train[i][j][1]&&i+v[j-1]<=T)dp[i][j]=min(dp[i][j],dp[i+v[j-1]][j-1]); //右走}printf("Case Number %d: ",ca++);if (dp[0][1]>=INF) puts("impossible");else printf("%d\n",dp[0][1]);}}

總結(jié)

以上是生活随笔為你收集整理的uva 1025——A Spy in the Metro的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。