首页 > 代码库 > World Finals 2003 UVA - 1025 A Spy in the Metro（动态规划）
World Finals 2003 UVA - 1025 A Spy in the Metro（动态规划）
分析：时间是一个天然的序，这个题目中应该决策的只有时间和车站，使用dp[i][j]表示到达i时间，j车站在地上已经等待的最小时间，决策方式有三种，第一种：等待一秒钟转移到dp[i+1][j]的状态，代价为1。第二种：如果可以则向右上车，转移到dp[i+t][j+1],无代价，t为列车行驶时间。第三种与第二种相同。初始状态为dp[0][1] = 0，其他为INF。答案为dp[T][n]。
代码如下：
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<map>using namespace std;#define N 55#define INF 1e9bool gol[N][N*4],gor[N][N*4];int dp[N*4][N];int main(){ int n,T,t[N],m1,m2,d,e,sum,ans,ca=0; while(cin>>n && n) { cin>>T; for(int i = 2; i <= n; i++) { cin>>t[i]; } memset(gol,false,sizeof(gol)); memset(gor,false,sizeof(gor)); cin>>m1; for(int i = 0; i < m1; i++) { cin>>d; gor[1][d] = true; sum = d; for(int j = 2; j <= n; j++) { sum += t[j]; gor[j][sum] = true; } } cin>>m2; for(int i = 0; i < m2; i++) { cin>>d; gol[n][d] = true; sum = d; for(int j = n-1; j >= 1; j--) { sum += t[j+1]; gol[j][sum] = true; } } for(int i = 0; i <= T; i++) { for(int j = 1; j <= n; j++) { dp[i][j] = INF; } } dp[0][1] = 0; for(int i = 0; i <= T; i++) { for(int j = 1; j <= n; j++) { if(i+1 <= T) dp[i+1][j] = min(dp[i][j]+1,dp[i+1][j]); if(j+1<=n&&gor[j][i]&&i+t[j+1]<=T)dp[i+t[j+1]][j+1]=min(dp[i+t[j+1]][j+1],dp[i][j]); if(j-1>=1&&gol[j][i]&&i+t[j]<=T)dp[i+t[j]][j-1]=min(dp[i+t[j]][j-1],dp[i][j]); } } printf("Case Number %d: ",++ca); if(dp[T][n] >= INF) ans = -1; else ans = dp[T][n]; if(ans == -1) printf("impossible\n"); else printf("%d\n",ans); } return 0;}
World Finals 2003 UVA - 1025 A Spy in the Metro（动态规划）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。