洛谷Luogu

洛谷Luogu"/>

洛谷Luogu

这个题不知道为什么就是 提高+/省选- 的题，感觉相对比较水，数据也小，搜索也能A吧，
这里讲 dp做法
首先定义状态，就是时间和地点，用 f[i][j]表示在i时,j车站的最少等待时间
转移方式最多有三种：
1、从上一秒转移 f[i][j]=min(f[i][j],f[i-1][j]);
2、有属于 M1 的车到站了 f[i][j]=min(f[i][j],f[i- 上一站到这一站的时间 ][j-1]);
3、有属于 M2 的车到站了 f[i][j]=min(f[i][j],f[i- 下一站到这一站的时间 ][j+1]);
然后就可以转移了

复杂度 O(N*T)

见代码：

#include <bits/stdc++.h>
#define mem(s,x)  memset(s,x,sizeof(s))
#define fr(i,n,m) for (int i=n;i<=m;i++)
using namespace std;
int n,p,t[55],m1,t1[55],m2,t2[55];
int f[205][55];//在i时，第j个车站等待的时间 
int vis[205][55][2];//在 i 时,第 j 个车站是否有车从 k 方向来 
void memset_5(){mem(f,127);mem(vis,0);mem(t,0);mem(t1,0);mem(t2,0);}    
void work(int kase){int tmp;fr(i,1,m1){tmp=t1[i];for(int j=1;j<=n&&tmp<=p;j++){vis[tmp][j][0]=1;tmp+=t[j];}}fr(i,1,m2){tmp=t2[i];for(int j=n;j>=1&&tmp<=p;j--){vis[tmp][j][1]=1;tmp+=t[j-1];}}f[0][1]=0;fr(i,1,p) fr(j,1,n){f[i][j]=min(f[i][j],f[i-1][j]+1);if(vis[i][j][0]==1) f[i][j]=min(f[i][j],f[i-t[j-1]][j-1]);if(vis[i][j][1]==1) f[i][j]=min(f[i][j],f[i-t[j]][j+1]); }if(f[p][n]<=p) printf("Case Number %d: %d\n",kase,f[p][n]);else printf("Case Number %d: impossible\n",kase);
}
int main(){int kase=1;scanf("%d",&n);while(n!=0){memset_5();scanf("%d",&p);fr(i,1,n-1) scanf("%d",&t[i]);scanf("%d",&m1);fr(i,1,m1) scanf("%d",&t1[i]);scanf("%d",&m2);fr(i,1,m2) scanf("%d",&t2[i]);work(kase++);scanf("%d",&n);}
}