一个间谍要从第1个车站到第n个车站在T时刻与人接头。她可以灵活地在车站在各列车上穿梭，求在车站等待的最短时间。
书上给出了思路和主程序代码，剩下的就是输入了，用has_train存每个时刻每个车站的状态。每读入一辆车，就模拟至目标时间，储存它经过的站点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=55,maxt=210;
const int INF=1<<30;
int t[maxn],dp[maxt][maxn];
bool has_train[maxt][maxn][2];
int main(){
int n,T,tt=0;
while(cin>>n,n){
memset(has_train,0,sizeof(has_train));
int m1,m2,d;
cin>>T;
for(int i=1;i<n;++i) cin>>t[i];
cin>>m1;
while(m1--&&cin>>d)
for(int i=1;i<n;d+=t[i++])
if(d<=T) has_train[d][i][0]=true;
cin>>m2;
while(m2--&&cin>>d)
for(int i=n-1;i>0;d+=t[i--])
if(d<=T) has_train[d][i+1][1]=true;
for(int i=1;i<n;++i) dp[T][i]=INF;
dp[T][n]=0;
for(int i=T-1;i>=0;--i)
for(int j=1;j<=n;++j){
dp[i][j]=dp[i+1][j]+1;
if(j<n&&has_train[i][j][0]&&i+t[j]<=T)
dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]);
if(j>1&&has_train[i][j][1]&&i+t[j-1]<=T)
dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]);
}
cout<<"Case Number "<<++tt<< ": ";
if(dp[0][1]>=INF) cout<<"impossible\n";
else cout<<dp[0][1]<<"\n";
}
return 0;
}
|
** 本文迁移自我的CSDN博客，格式可能有所偏差。 **