題目鏈接：https://cn.vjudge.net/problem/UVA-1025

題目大意：Mario從第1站出發(fā)，目的是在時(shí)刻T會(huì)見(jiàn)車站 $n$ 的一個(gè)間諜。由于在車站等待容易被抓，所以應(yīng)盡量躲在開(kāi)動(dòng)的火車上，即在車站等待的時(shí)間最短，且Mario十分敏捷，及時(shí)兩輛方向不同的列車在同一時(shí)間?？?#xff0c;她也能完成換乘。
輸入的第1行為 $n(2\le n\le 50)$ ，第2行為 $T(0\le T\le 200)$ ，第3行有 $n?1$ 個(gè)整數(shù) $t_1,t_2,\dots ,t_{n?1}$$(1\le t_i\le 70)$ ，其中 $t_i$ 表示地鐵從車站 $i$ 到車站 $i+1$ 的行駛時(shí)間（兩個(gè)方向一樣）。第4行為 $M1(1\le M1\le 50)$，即從第1站出發(fā)向右開(kāi)的列車數(shù)目。第5行包含 $M1$ 個(gè)整數(shù) $d_1,d_2,\dots ,d_{M1}(0\le d_i\le 250,d_i<d_{i+1})$ ，即各列車的出發(fā)時(shí)間。第6、7行描述從第 $n$ 站出發(fā)向左開(kāi)的列車，格式同第4、5行。輸出僅包含1行，即最少等待時(shí)間。無(wú)解輸出 impossible.

解題思路：用 $dp[i][j]$ 來(lái)代表第 $i$ 時(shí)刻在 $j$ 車站的等待時(shí)間。在每一個(gè)車站，Mario有三種方法：1、等待1分鐘
2、搭乘向左開(kāi)的列車
3、搭乘向右開(kāi)的列車
我們可以先假設(shè)終態(tài)為 $dp[T][n]=0$ ，然后再由終態(tài)往前推始態(tài) $dp[0][1]$ ，如果 $dp[0][1]\ge inf$，則證明無(wú)法推到，輸出impossible，否則輸出 $dp[0][1]$ 的值即可。

代碼：

#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <cstdlib> #include <cstring> #include <map> #include <stack> #include <queue> #include <vector> #include <bitset> #include <set> #include <utility> #include <sstream> #include <iomanip> using namespace std; typedef long long ll; typedef unsigned long long ull; #define inf 0x3f3f3f3f #define rep(i,l,r) for(int i=l;i<=r;i++) #define lep(i,l,r) for(int i=l;i>=r;i--) #define ms(arr) memset(arr,0,sizeof(arr)) //priority_queue<int,vector<int> ,greater<int> >q; const int maxn = (int)1e5 + 5; const ll mod = 1e9+7; int dp[1200][120]; int d1[1200][120],d2[1200][120]; int t[120]; int sum1[120],sum2[120]; int main() {#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);ios::sync_with_stdio(0),cin.tie(0);int n,T,c=0;while(scanf("%d",&n)!=EOF) {if(n==0) break;c++;ms(sum1);ms(sum2);ms(d1);ms(d2);ms(t);scanf("%d",&T);rep(i,1,n-1) {scanf("%d",&t[i]);sum1[i]=sum1[i-1]+t[i];}lep(i,n-1,1) sum2[i]=sum2[i+1]+t[i];int m1,m2;scanf("%d",&m1);int nape;rep(i,1,m1) {scanf("%d",&nape);d1[nape][1]=1;rep(j,1,n-1) {d1[nape+sum1[j]][j+1]=1;}}scanf("%d",&m2);rep(i,1,m2) {scanf("%d",&nape);d2[nape][n]=1;lep(j,n-1,1) {d2[nape+sum2[j]][j]=1;}}rep(i,1,n-1) dp[T][i]=inf;dp[T][n]=0;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&&d1[i][j]==1&&i+t[j]<=T)dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]);if(j>1&&d2[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: ",c);if(dp[0][1]>=inf) printf("impossible\n");else printf("%d\n",dp[0][1]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的UVA1025——A Spy in the Metro【dp】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。