UVa1025 A_Spy_in_the_Metro

2019-11-08 02:57:26

字体：大中小

来源：转载

供稿：网友

UVa1025 A_Spy_in_the_Metro

动态规划经典题目

思路：

影响到决策的只有当前时间和所处的车站，可以用f[i][j] $f[i][j]$ 表示当前时刻i，在车站j，还需要等待的时间用bool ht[t][i][d]表示在i车站在t时刻向d方向有没有火车(d=0表示向右，1向左)时间复杂度：O(NT) $O(NT)$ 可以得出状态转移方程： f[i][j]=min⎧⎩⎨f[i+1][j]+1f[i+t[j]][j+1](j<N、i+t[j]<=T、ht[i][j][0])f[i+t[j−1]][j−1](j>1、i+t[j−1]<=T、ht[i][j][1]) $/begin{equation} f[i][j]=min /begin{cases}f[i+1][j]+1//f[i+t[j]][j+1]/<a href="http://www.VeVb.com/qq.asp">QQ</a>uad(j<N、i+t[j]<=T、ht[i][j][0])//f[i+t[j-1]][j-1]/qquad(j>1、i+t[j-1]<=T、ht[i][j][1]) /end{cases}/end{equation}$

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int MAXN=50,MAXT=200,INF = 1000000000;int dp[MAXT+1][MAXN+1];bool ht[MAXT+1][MAXN+1][2];int t[MAXN+1];int casecnt;int main(){ int N,T,M1,M2; while(scanf("%d%d",&N,&T)&&N) { int i,j,x; for(i=1;i<N;i++) scanf("%d",&t[i]); memset(ht,false,sizeof(ht)); scanf("%d",&M1); while(M1--) { scanf("%d",&x); for(j=1;j<N;j++) { if(x>T) break; ht[x][j][0]=true;x+=t[j]; } } scanf("%d",&M2); while(M2--) { scanf("%d",&x); for(j=N-1;j>=1;j--) { if(x>T) break; ht[x][j+1][1]=true;x+=t[j]; } } for(int i = 1; i < N; i++) dp[T][i] = INF; dp[T][N]=0; for(i=T-1;i>=0;i--) for(j=1;j<=N;j++) { dp[i][j]=dp[i+1][j]+1; if(j<N && i+t[j]<=T && ht[i][j][0]) dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]); if(j>1 && i+t[j-1]<=T && ht[i][j][1]) dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]); } PRintf("Case Number %d: ",++casecnt); if(dp[0][1]<(int)1e9) printf("%d/n",dp[0][1]); else printf("impossible/n"); } return 0;}

上一篇：XSL语言的三种模式

下一篇：PAT 1027

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注