UVa 1025 A Spy in the Metro

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=35913

预处理出每个时间、每个车站是否有火车

为了方便判断是否可行,倒推处理,每次有三种决策:原地坐等一分钟、搭车向左(如果有车)、搭车向右(如果有车)

 /**/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int mxn=;
int n,T;
bool h[mxn][mxn][];
int ti[mxn];
int m,d,e;
int f[mxn][mxn];
void clear(){
memset(ti,,sizeof(ti));
memset(h,,sizeof(h));
memset(f,,sizeof(f));
}
int main(){
int cnt=;
while(scanf("%d",&n) && n){
clear();
scanf("%d",&T);
int i,j;
for(i=;i<n;i++)scanf("%d",&ti[i]);//车站距离
scanf("%d",&m);
for(i=;i<=m;i++)
{
scanf("%d",&d);//左边发车时间
for(j=;d<=T && j<=n;d+=ti[j],j++){
h[d][j][]=;
}
}
scanf("%d",&m);
for(i=;i<=m;i++)
{
scanf("%d",&e);//右边发车时间
for(j=n;e<=T && j>=;j--,e+=ti[j]){
h[e][j][]=;
}
}
//以上全是初始化
f[T][n]=;
for(i=T-;i>=;i--){//倒推
for(j=;j<=n;j++){
f[i][j]=f[i+][j]+;//等待
if(j<n && h[i][j][] && i+ti[j]<=T)
f[i][j]=min(f[i][j],f[i+ti[j]][j+]);//向右
if(j> && h[i][j][] && i+ti[j-]<=T)
f[i][j]=min(f[i][j],f[i+ti[j-]][j-]);//向左
}
}
printf("Case Number %d: ",++cnt);
if(f[][]>=0xff) printf("impossible\n");
else printf("%d\n",f[][]);
}
return ;
}
上一篇:DLLHijack漏洞原理


下一篇:Bootstrap输入框组