题目大意：
有一个线性城市，城市里有火车再走，给出两个城市之间火车需要走的时间以及每个火车从左端点或右端点出发的时间
已知一个人想要在T时刻到达n城市，求他在过程中所有在车站等待时间的最小值
思路：
dp(i,j)表示j时刻在i车站的最小等待值
先预处理出所有时刻某车站是否有车
然后直接dp
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<cstdlib> 6 #include<vector> 7 #include<queue> 8 #include<algorithm> 9 #define inf 2147483611 10 #define ll long long 11 #define MAXN 55 12 #define MOD 13 using namespace std; 14 inline int read() 15 { 16 int x=0,f=1; 17 char ch;ch=getchar(); 18 while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} 19 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} 20 return x*f; 21 } 22 int n,t[MAXN],m,x,dp[MAXN][MAXN*5],cnt; 23 bool larv[MAXN][MAXN*4],rarv[MAXN][MAXN*4]; 24 int main() 25 { 26 while(scanf("%d",&n)&&n) 27 { 28 memset(larv,0,sizeof(larv)); 29 memset(rarv,0,sizeof(rarv)); 30 int tm=read(); 31 for(int i=1;i<n;i++) t[i]=read(); 32 m=read(); 33 for(int i=1;i<=m;i++) 34 { 35 x=read(); 36 for(int j=1;j<=n&&x<=tm;j++) {larv[j][x]=1;x+=t[j];} 37 } 38 m=read(); 39 for(int i=1;i<=m;i++) 40 { 41 x=read(); 42 for(int j=n;j>=1&&x<=tm;j--) {rarv[j][x]=1;x+=t[j-1];} 43 } 44 memset(dp,127,sizeof(dp)); 45 dp[1][0]=0; 46 for(int i=1;i<=tm;i++) 47 { 48 for(int j=1;j<=n;j++) 49 { 50 dp[j][i]=dp[j][i-1]+1; 51 if(larv[j][i]) dp[j][i]=min(dp[j][i],dp[j-1][i-t[j-1]]); 52 if(rarv[j][i]) dp[j][i]=min(dp[j][i],dp[j+1][i-t[j]]); 53 } 54 } 55 printf("Case Number %d: ",++cnt); 56 if(dp[n][tm]>=2139062143) printf("impossible "); 57 else printf("%d ",dp[n][tm]); 58 } 59 return 0; 60 }