本文主要是介绍dp专题 lrj-p269 uva A Spy in the Metro 2003wf，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
lrj 入门经典 p267
从本题得到的收获：
分清主线：
影响决策的只有时间以及所处的车站
理清次线：
火车跑来跑去的，我们需要处理好他们，为我们的主线服务，即，在某些车站的时候，是否有车在这个时间
故令 dp【】【】，第一维表示时刻，第二维表示在某车站出发，需要等待的时间
写dp就要注意：初始化条件：
这里的初始化条件就是dp【T】【i】为INF，但是在终点（边界），我们却初始化为0，因为递推的方向
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;#define INF 0x3f3f3f3f
int time[25];
int dp[300][300];
int has_train[300][300][3];int main()
{int n,t,m1,m2,temp,cases=1;//freopen("in.txt","r",stdin);while(scanf("%d",&n),n!=0){scanf("%d",&t);for(int i=1;i<=n-1;i++)scanf("%d",&time[i]);memset(has_train,0,sizeof(has_train));scanf("%d",&m1);for(int i=1;i<=m1;i++){scanf("%d",&temp);has_train[temp][1][0]=1;for(int j=1;j<=n-1;j++){has_train[temp+time[j]][j+1][0]=1;temp+=time[j];}}scanf("%d",&m2);for(int i=1;i<=m2;i++){scanf("%d",&temp);has_train[temp][n][1]=1;for(int j=n-1;j>=1;j--){has_train[temp+time[j]][j][1]=1;temp+=time[j];}}for(int i=1;i<=n;i++)dp[t][i]=INF;dp[t][n]=0;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&&has_train[i][j][0]&&i+time[j]<=t)dp[i][j]=min(dp[i][j],dp[i+time[j]][j+1]);if(j>1&&has_train[i][j][1]&&i+time[j-1]<=t)dp[i][j]=min(dp[i][j],dp[i+time[j-1]][j-1]);}}printf("Case Number %d: ",cases++);if(dp[0][1]>=INF) puts("impossible");else printf("%d\n",dp[0][1]);}return 0;
}这篇关于dp专题 lrj-p269 uva A Spy in the Metro 2003wf的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
