UVA1025 Thematic Contests

题目链接：

题意：有N个站台，最终时间T，然后N-1个数表示每两个站台之间需要的时间，然后再给一个M1表示有M1个发车时间，表示从左到右这个方向的火车的发车时间，以及一个M2和M2个数表示从左到右这个方向的火车的发车时间。问这个人从1站台出发，T时刻要到达N站台，但要停留在站台上的时间最少，也就是说尽可能多的时间在火车上

比如第一个样例：
4
55
5 10 15
4
0 5 10 20
4
0 5 10 15

先从①站台坐两站用时15分钟到第③站台，然后用10分钟做回②站台，再用25分钟一口气做到④站台，然后在④站台这里等5分钟时间到达55分钟，并且到了最后一站，并且在站台上等的时间最少

思路：
本来dp就不行，然后看到这道题就不是那种一眼就能反应过来是dp的，我连dp的状态都没有构建好，一开始还想会不会是区间dp，i站台到j站台的最少时间T_T

最后看题解，题解说==时间是单向流逝的，是一个天然的“序”==用dp[t][i]来表示到了t时间人在i站台这里，人要么等火车，要么坐火车走

我看了这个恍然大悟，可不是嘛，时间一确定，人所在的站台一确定，那就什么都确定了啊，这不是就把所有的情况都列举完了嘛~诶，到这里我感觉我对“dp就是优雅的枚举”这话又理解了一点，这道题其实只要把dp[t][i]构建好，方程其实是非常好推出来的

但是我为什么RE呀T_T
后来在clf学弟大佬滴帮助下，终于找到。。。原来是我那里的i没有写范围，当时写的时候想当然的不会超过，以后真是，管他会不会多余哟，没有害处的都写起T_T

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=2000+5;
int dp[maxn][maxn];//dp[t][i]表示在第t分钟时的位置是在第i个车站在车外等待的最少时间 
int a[maxn][maxn];//a[i][j]表示从第i站到第j站需要的时间 
int st1[maxn],st2[maxn];//表示顺着和逆着火车的发车时间 
bool d1[maxn][maxn],d2[maxn][maxn];//d1[t][i]表示时间t时顺着的或者是否在i站停车 
int main()
{
	for(int Case=1;;Case++)
	{
		memset(dp,0x3f,sizeof dp);
		dp[0][1]=0;
		memset(d1,0,sizeof d1);
		memset(d2,0,sizeof d2);
		int N,T;
		cin>>N;
		if(N==0)break;
		cin>>T;
		for(int i=1; i<N; i++)
		{
			int t;
			cin>>t;
			a[i][i+1]=a[i+1][i]=t;
		}
		int M1,M2;
		cin>>M1;
		for(int k=1;k<=M1;k++)
		{
			cin>>st1[k];
			for(int t=st1[k],i=1;t<=T,i<=N;i++)//这里i没有写i<=N,以及下面的i也没有写范围,导致RE了好久 
			{
				d1[t][i]=1;
				t+=a[i][i+1];
			}
		}
		cin>>M2;
		for(int k=M2;k>=1;k--)
		{
			cin>>st2[k];
			for(int t=st2[k],i=N;t<=T,i>=1;i--)//这里也要写i>=1,不然就有可能跑到负数导致RE 
			{
				d2[t][i]=1;
				t+=a[i][i-1];
			}
		}
		for(int t=1; t<=T; t++)
		{
			for(int i=1; i<=N; i++)
			{
				dp[t][i]=min(dp[t][i],dp[t-1][i]+1);//原地等待
				if(i-1>=1 && t-a[i-1][i]>=0 && d1[t-a[i-1][i]][i-1])dp[t][i]=min(dp[t][i],dp[t-a[i-1][i]][i-1]);//从第i-1个站过来
				if(i+1<=N && t-a[i+1][i]>=0 && d2[t-a[i+1][i]][i+1])dp[t][i]=min(dp[t][i],dp[t-a[i+1][i]][i+1]);//从第i+1个站过来
			}
		}
		int inf=0x3f3f3f3f; 
		if(dp[T][N]==inf)cout<<"Case Number "<<Case<<": "<<"impossible"<<endl;
		else cout<<"Case Number "<<Case<<": "<<dp[T][N]<<endl;
	}
}