uva 1025——A Spy in the Metro
题意:有一个线性的车站(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 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]);
}
}
还没有评论,来说两句吧...