World Finals 2003 UVA - 1025 A Spy in the Metro(动态规划)

  分析:时间是一个天然的序,这个题目中应该决策的只有时间和车站,使用dp[i][j]表示到达i时间,j车站在地上已经等待的最小时间,决策方式有三种,第一种:等待一秒钟转移到dp[i+1][j]的状态,代价为1。第二种:如果可以则向右上车,转移到dp[i+t][j+1],无代价,t为列车行驶时间。第三种与第二种相同。初始状态为dp[0][1] = 0,其他为INF。答案为dp[T][n]。

  代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
#define N 55
#define INF 1e9
bool gol[N][N*],gor[N][N*];
int dp[N*][N];
int main()
{
int n,T,t[N],m1,m2,d,e,sum,ans,ca=;
while(cin>>n && n)
{
cin>>T;
for(int i = ; i <= n; i++)
{
cin>>t[i];
}
memset(gol,false,sizeof(gol));
memset(gor,false,sizeof(gor));
cin>>m1;
for(int i = ; i < m1; i++)
{
cin>>d;
gor[][d] = true;
sum = d;
for(int j = ; j <= n; j++)
{
sum += t[j];
gor[j][sum] = true;
}
}
cin>>m2;
for(int i = ; i < m2; i++)
{
cin>>d;
gol[n][d] = true;
sum = d;
for(int j = n-; j >= ; j--)
{
sum += t[j+];
gol[j][sum] = true;
}
}
for(int i = ; i <= T; i++)
{
for(int j = ; j <= n; j++)
{
dp[i][j] = INF;
}
}
dp[][] = ;
for(int i = ; i <= T; i++)
{
for(int j = ; j <= n; j++)
{
if(i+ <= T) dp[i+][j] = min(dp[i][j]+,dp[i+][j]);
if(j+<=n&&gor[j][i]&&i+t[j+]<=T)dp[i+t[j+]][j+]=min(dp[i+t[j+]][j+],dp[i][j]);
if(j->=&&gol[j][i]&&i+t[j]<=T)dp[i+t[j]][j-]=min(dp[i+t[j]][j-],dp[i][j]);
}
}
printf("Case Number %d: ",++ca);
if(dp[T][n] >= INF) ans = -;
else ans = dp[T][n];
if(ans == -) printf("impossible\n");
else printf("%d\n",ans);
}
return ;
}
上一篇:CentOS上安装FastDFS分布式文件系统


下一篇:线段树 + 区间更新 ----- HDU 4902 : Nice boat