非常有价值的dp题目 也是我做的第一题dp 真的效率好高
题意：某城市的地铁是线性的 有n个车站 从左到右编号为1-n 有m1辆列车从第一站开始往右开 还有m2辆列车从第n站开始往左开 在时刻0 小明从第1站出发 目的是在时刻T 正好会见在第n站的间谍 为了不被抓 小明在车站等待的时间要尽量少 求出最短时间 如果到不了 输出impossible
输入第一行为n 第二行为T 第三行有n-1个数字 表示 从左到右两个车站之间列车行驶的时间 接下来为m1 然后跟着m1个数字 表示车站1发车时刻 然后m2 同理
一开始根本想不到用dp 这题的元素好多 ！！
每次有三种决策
1 原地等待1s
2 搭乘往右的车 （当然 前提是有）
3 搭乘往左的车
当面临多决策问题时 且所处环境（时间 地点）多样时 用dp做！！！
影响决策的元素只有两个 1 时间 2 所处车站
所以 dp i j i表示当前时刻 j 表示所处车站
从结束点 也就是 时刻为T时开始进行dp
注意对dp数组的初始化 都在i=T的情况下 当i==n时 达成目标 dp为0 当i为其他值时 全部为inf（显然已经没机会了）
非常好的dp ！！
#include<bits/stdc++.h> using namespace std; #define N 200+5 #define inf 0x3f3f3f3f int n,t[N],car[N][N][2]; int dp[N][N]; int main() { int cas=0; int T; int q; int x; while(scanf("%d",&n)==1,n) { memset(car,0,sizeof car); scanf("%d",&T); for(int i=0;i<n-1;i++)scanf("%d",&t[i]); scanf("%d",&q); while(q--) { scanf("%d",&x); car[0][x][0]=1; for(int i=1;i<n;i++) { x+=t[i-1]; car[i][ x ][0]=1; } } scanf("%d",&q); while(q--) { scanf("%d",&x); car[n-1][x][1]=1; for(int i=n-2;i>=0;i--) { x+=t[i]; car[i][x][1]=1; } } for(int i=0;i<n-1;i++)dp[T][i]=inf;//其他的完全不用初始化 填表会全部覆盖掉 dp[T][n-1]=0; for(int i=T-1;i>=0;i--)//顺序必须是固定的 for(int j=0;j<n;j++) { dp[i][j]=dp[i+1][j]+1;//原地等待一秒钟 if( car[j][i][0] && i+t[j]<=T && j<n-1 ) dp[i][j]=min(dp[i][j],dp[ i+t[j] ][j+1] ); if( car[j][i][1] && j!=0 && i+t[j-1]<=T ) dp[i][j]=min(dp[i][j],dp[ i+t[j-1] ][j-1]); } printf("Case Number %d: ",++cas); if(dp[0][0]>=inf) printf("impossible "); else printf("%d ",dp[0][0]); } return 0; }