首页 > 代码库 > UVA1025 A Spy in the Metro
UVA1025 A Spy in the Metro
题解:
dp[i][j]表示在i时刻,在车站j。可以往哪行动
预处理一下每个时刻,每个车站是否有车
有3个决策
1.等1分钟 dp[i][j]=dp[i+1][j]+1
2.向左 dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1])
3.向右 dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1])
初始状态是dp[T][n]=0;
代码:
#include<bits/stdc++.h>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x)) #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 #define INF 1e9typedef pair<int,int> P;const double eps=1e-9;const int maxnnode=11000;const int maxn=100100;const int mod=20071027;int has_train[205][75][2],t[75];int dp[205][75];int n,T,m1,m2,M1,M2;int main(){ int Kase=1; while(~scanf("%d",&n)&&n){ CLR(has_train); CLR(dp); scanf("%d",&T); for(int i=1;i<=n-1;i++) scanf("%d",&t[i]); scanf("%d",&m1); for(int i=1;i<=m1;i++) { scanf("%d",&M1); for(int j=1;j<=n-1;j++) { if(M1<=T) has_train[M1][j][0]=1; M1+=t[j]; } } scanf("%d",&m2); for(int i=1;i<=m2;i++) { scanf("%d",&M2); for(int j=n-1;j>=1;j--) { if(M2<=T) has_train[M2][j+1][1]=1; M2+=t[j]; } } dp[T][n]=0; for(int i=1;i<=n-1;i++) dp[T][i]=INF; 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]); } printf("Case Number %d: ",Kase++); if(dp[0][1]>=INF) printf("impossible\n"); else printf("%d\n",dp[0][1]); } return 0;}
UVA1025 A Spy in the Metro
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。