UVa1025 A_Spy_in_the_Metro

2019-11-08 02:57:26

字體：大中小

供稿：網(wǎng)友

UVa1025 A_Spy_in_the_Metro

動態(tài)規(guī)劃經(jīng)典題目

思路：

影響到?jīng)Q策的只有當(dāng)前時間和所處的車站，可以用f[i][j] $f[i][j]$ 表示當(dāng)前時刻i，在車站j，還需要等待的時間用bool ht[t][i][d]表示在i車站在t時刻向d方向有沒有火車(d=0表示向右，1向左)時間復(fù)雜度：O(NT) $O(NT)$ 可以得出狀態(tài)轉(zhuǎn)移方程： 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.survivalescaperooms.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]); }