UVa 1025A Spy in the Metro;DAG动态规划

题目链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=245&page=show_problem&problem=3466

典型的DAG应用

#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
const int INF = (1<<21);
int main()
{
	int n,t,o=1,x,right,left;
	int a[maxn],dp[302][maxn];
	int train[305][maxn][2];
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)	return 0;
		scanf("%d",&t);
		memset(train,0,sizeof(train));
		for(int i=1;i<n;i++)	dp[t][i]=INF;
		dp[t][n]=0;
		for(int i=1;i<n;i++)	
			scanf("%d",&a[i]);//a[i]表示车站i到车站i+1的行驶时间 
		scanf("%d",&right);
		for(int i=1;i<=right;i++)
		{
			scanf("%d",&x);
			for(int j=1;j<=n;j++)
			{
				train[x][j][0]=1;
				x+=a[j];
			}
		}
		scanf("%d",&left);
		for(int i=1;i<=left;i++)
		{
			scanf("%d",&x);
			for(int j=n;j>=1;j--)
			{	
				train[x][j][1]=1;			
				x+=a[j-1];
			} 
		}
		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&&train[i][j][0]&&a[j]+i<=t)
					dp[i][j]=min(dp[i][j],dp[i+a[j]][j+1]);//上向右开的车 
				if(j>1&&train[i][j][1]&&a[j-1]+i<=t)
					dp[i][j]=min(dp[i][j],dp[i+a[j-1]][j-1]);//上向左开的车 
			}
		}
		printf("Case Number %d: ",o);
		if(dp[0][1]<INF)
			printf("%d\n",dp[0][1]);
		else
			printf("impossible\n");
		o++;
	}

	return 0;
}