题目描述
特工玛利亚被送到S市执行一个特别危险的任务。她需要利用地铁完成他的任务,S市的地铁只有一条线路运行,所以并不复杂。
玛利亚有一个任务,现在的时间为0,她要从第一个站出发,并在最后一站的间谍碰头。玛利亚知道有一个强大的组织正在追踪她,她知道如果一直呆在一个车站,她会有很大的被抓的风险,躲在运行的列车中是比较安全的。所以,她决定尽可能地呆在运行的列车中,她只能往前或往后坐车。
玛利亚为了能准时且安全的到达最后一个车站与对方碰头,需要知道在在车站最小等待时间总和的计划。你必须写一个程序,得到玛丽亚最短的等待时间。当然,到了终点站之后如果时间还没有到规定的时刻,她可以在车站里等着对方,只不过这个等待的时刻也是要算进去的。
这个城市有n个车站,编号是1-n,火车是这么移动的:从第一个车站开到最后一个车站。或者从最后一站发车然后开会来。火车在每特定两站之间行驶的时间是固定的,我们也可以忽略停车的时间,玛利亚的速度极快,所以他可以迅速上下车即使两辆车同时到站。
输入输出格式
输入格式: 输入文件包含多组数据,每组数据都由7行组成
第1行:一个正整数N(2<=N<=50)表示站的数量
第2行:一个正整数T(0<=T<=200)表示需要的碰头时间
第3行:1-(n-1)个正整数(0<ti<70)表示两站之间列车的通过时间
第4行:一个整数M1(1<=M1<=50)表示离开第一个车站的火车的数量
第5行:M1个正整数:d1,d2……dn,(0<=d<=250且di<di+1)表示每一列火车离开第一站的时间
第6行:一个正整数M2(1<=M2<=50)表示离开第N站的火车的数量
第7行:M2个正整数:e1,e2……eM2,(0<=e<=250且ei<ei+1)表示每一列火车离开第N站的时间
最后一行有一个整数0。
输出格式: 对于每个测试案例,打印一行“Case Number N: ”(N从1开始)和一个整数表示总等待的最短时间或者一个单词“impossible”如果玛丽亚不可能做到。按照样例的输出格式。
输入输出样例
输入样例#1:
4
55
5 10 15
4
0 5 10 20
4
0 5 10 15
4
18
1 2 3
5
0 3 6 10 12
6
0 3 5 7 12 15
2
30
20
1
20
7
1 3 5 7 11 13 17
0
输出样例#1:
Case Number 1: 5
Case Number 2: 0
Case Number 3: impossible
说明
第一组样例说明,她0分钟时上车,在3号站下车,立刻坐上(0分始发)15分开的车回去,到2号车站,立刻坐上(20分始发)25开的车到终点,50分到,还需要等待5分钟。
解题报告:
这个题不知道为什么就是 提高+/省选- 的题,感觉相对比较水,数据也小,搜索也能A
首先定义状态,就是时间和地点,用 f[i][j] 表示在 i 时, j 车站的最少等待时间 转移方式最多有三种:
1、从上一秒转移 f[i][j]=min(f[i][j],f[i-1][j]);
2、有属于 M1 的车到站了 f[i][j]=min(f[i][j],f[i- 上一站到这一站的时间 ][j-1]);
3、有属于 M2 的车到站了 f[i][j]=min(f[i][j],f[i- 下一站到这一站的时间 ][j+1]); 然后就可以转移了 复杂度 O(N*T)
上代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,p,t[],m1,t1[],m2,t2[];
int f[][];//在i时,第j个车站等待的时间
bool vis[][][];//在 i 时,第 j 个车站是否有车从 k 方向来
void init(){
memset(f,,sizeof(f));
memset(vis,,sizeof(vis));
memset(t,,sizeof(t));
memset(t1,,sizeof(t1));
memset(t2,,sizeof(t2));
} void work(int num){
int tmp;
for(int i=;i<=m1;i++){
tmp=t1[i];
for(int j=;j<=n&&tmp<=p;j++){
vis[tmp][j][]=;
tmp+=t[j];
}
}
for(int i=;i<=m2;i++){
tmp=t2[i];
for(int j=n;j>=&&tmp<=p;j--){
vis[tmp][j][]=;
tmp+=t[j-];
}
}
f[][]=;
for(int i=;i<=p;i++){
for(int j=;j<=n;j++){
f[i][j]=min(f[i][j],f[i-][j]+);
if(vis[i][j][]==){
f[i][j]=min(f[i][j],f[i-t[j-]][j-]);
}
if(vis[i][j][]==){
f[i][j]=min(f[i][j],f[i-t[j]][j+]);
}
}
}
if(f[p][n]<=p){
printf("Case Number %d: %d\n",num,f[p][n]);
}
else{
printf("Case Number %d: impossible\n",num);
}
} int main(){
int num=;
scanf("%d",&n);
while(n!=){
init();
scanf("%d",&p);
for(int i=;i<=n-;i++){
scanf("%d",&t[i]);
}
scanf("%d",&m1);
for(int i=;i<=m1;i++){
scanf("%d",&t1[i]);
}
scanf("%d",&m2);
for(int i=;i<=m2;i++){
scanf("%d",&t2[i]);
}
work(num++);
scanf("%d",&n);
}
}