[Ctsc2000]公路巡逻

HDU BZOJ

Time Limit: 10(1) Sec Memory Limit: 128 MB

Description 在一条没有分岔的高速公路上有n个关口，相邻两个关口之间的距离都是10km。所有车辆在这条高速公路上的最低速度为60km/h，最高速度为120km/h，并且只能在关口处改变速度。 巡逻的方式是在某个时刻Ti从第ni个关口派出一辆巡逻车匀速驶抵第(ni+1)个关口，路上耗费的时间为ti秒。 两辆车相遇是指它们之间发生超车或者两车同时到达某关口（同时出发不算相遇）。 巡逻部门想知道一辆于6点整从第1个关口出发去第n个关口的车（称为目标车）最少会与多少辆巡逻车相遇，请编程计算之。假设所有车辆到达关口的时刻都是整秒。

Input 输入文件第一行为两个用空格隔开的整数，分别为关口数n和巡逻车数m。（1< n < 50,1 < m < 300），接下来的m行每一行为一辆巡逻车的信息（按出发位置递增排序），格式为ni　Ti　ti，三项用空格隔开，分别表示第i辆巡逻车的出发位置、出发时刻和路上耗费的时间，其中ni和ti为整数，Ti形如hhmmss，表示时、分、秒，采用24小时制，不足两位的数用前置0补齐。（1 <= ni < n,05:00:00 <= Ti <= 23:00:00,300 <= ti <= 600）

Output 输出文件第一行为目标车与巡逻车相遇次数。第二行为目标车与巡逻车相遇次数最少时最早到达第n个关口的时刻（格式同输入中的Ti）。

Sample Input 3 2 1 060000 301 2 060300 600

Sample Output 0 061301

好吧，我承认我调了一下午的代码直到第二天早上才想出错误点。。。。。 现在说正解，因为hdu和bzoj上是10s的时限，所以不加优化也可以过。

设 dp[i][j] 表示在第j秒到达第i个关口最少和巡逻车的相遇次数。 那么当前状态就有可能从上一个关口某一个时间点转移过来，说具体一点，就是 [j−600s,j−300s] 的时候（因为每两个关口行驶时间最小为300s，最大为600s） 有转移方程式:

dp[i][j]=dp[i−1][j−k]+count(i−1,j−k,j)|j∈[(i−1)∗300,(i−1)∗600]且k∈[300,600]

至于 count(i,s,t) 是用来统计第s秒从第i个关口出发，t秒到达与巡逻车的相遇次数。 我们设每一辆从i出发的巡逻车出发时间为St，到达时间为Et。 如果 Et=t ，目标车和巡逻车一定在终点相遇； 如果 St<s且t<Et ，目标车追上了巡逻车，相遇； 如果 St>s且t>Et ，巡逻车追上了目标车，相遇。 如此我们就能计算出 count(i,s,t) 了。

#include<cstdio> #include<iostream> #include<cstring> #include<cmath> using namespace std; #define MAXN 50 #define MAXM 300 #define MAXT 30000 #define INF 0x3f3f3f3f typedef long long int LL; int St[MAXN+10][MAXM+10],Et[MAXN+10][MAXM+10]; int Cnt[MAXN+10]; int dp[MAXN+10][MAXT+10]; int N,K,M; int cal(int t) { return ((t/10000)-6)*3600+((t%10000)/100)*60+t%100; } int check(int pos,int s,int e) { int rn=0; for(int i=1;i<=Cnt[pos];++i) rn+=(Et[pos][i]==e||(St[pos][i]<s&&Et[pos][i]>e)||(St[pos][i]>s&&Et[pos][i]<e)); return rn; } void print(int t) { printf("ddd\n",6+t/3600,(t%3600)/60,t%60); } int main() { bool fir=1; while(~scanf("%d%d",&N,&K)) { if(!fir)puts(""); else fir=0; memset(Cnt,0,sizeof(Cnt)); int i,j,k; int a,b,c; for(i=1;i<=K;++i) { scanf("%d%d%d",&a,&b,&c); ++Cnt[a]; St[a][Cnt[a]]=cal(b); Et[a][Cnt[a]]=St[a][Cnt[a]]+c; } memset(dp,0x3f,sizeof(dp)); dp[1][0]=0; for(i=2;i<=N;++i) { int lt=(i-1)*300;//(i-1)*10*3600/120 int rt=(i-1)*600;;//(i-1)*10*3600/60; for(j=lt;j<=rt;++j) for(k=300;k<=600;++k) dp[i][j]=min(dp[i][j],dp[i-1][j-k]+check(i-1,j-k,j)); } int lt=(N-1)*300; int rt=(N-1)*600; int ans=INF,best; for(i=rt;i>=lt;--i) { if(ans>=dp[N][i]) { ans=dp[N][i]; best=i; } } printf("%d\n",ans); print(best); } } /* 3 2 1 060000 301 2 060300 600 3 2 1 060000 301 2 060300 600 */

那么现在HDU和BZOJ那10秒的坑爹时限就可以过了… /[> _ <]\可惜我们OJ是一秒….. 现在就有个神奇的优化动态规划算法的优化技巧（见倒数第二页）

对于同时从第i个关口出发的两辆目标车，设出发时间为s，到达时间为e(A)和e+1(B)。 对于每一辆从i出发的巡逻车: 若 Et<e 或者 Et>e ，则 A，B两车的相遇情况相同（无论是 St < s 还是 St > s） 若 Et=e ，当 St≤s 时，A相遇，B不相遇。 若 Et=e+1 ，当 St≥s 时，A不相遇，B相遇。 则

dp[i][j+1]−dp[i][j]=G(Et=e+1且St≥s)−G(Et=e且St≤s) （ G(P)表示满足条件P的巡逻车个数 ） 现在只用用 count(i,s,t) 求出 dp[i][j] 后再通过上述式子把它转化成dp[i][j+1]了。

需要注意的是， dp[i][j+1]−dp[i][j]=G(Et=e+1且St≥s)−G(Et=e且St≤s) 这个式子针对的是 S 相等的dp[i][j]和 dp[i][j+1] 。 所以我们不能直接取

dp[i][j+1]=min(dp[i][j+1],dp[i][j]+G(Et=e+1且St≥s)−G(Et=e且St≤s)) 因为现在的 dp[i][j] 是取 min 后的值，可能 S 与dp[i][j 1]不一致，所以我们可以用一个 tmp 数组临时记录一下。

#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<cstdlib> using namespace std; #define MAXN 50 #define MAXM 300 #define MAXT 30000 #define INF 0x3f3f3f3f typedef long long int LL; int St[MAXN+10][MAXM+10],Et[MAXN+10][MAXM+10]; int Cnt[MAXN+10]; int dp[MAXN+10][MAXT+10]; int G[310][2]; //辅助数组G[i][0]表示是满足Et==k且St>=T (T为你开的车的出发时刻) // G[i][1]表示是满足Et==k且St<=T 的巡逻车数 int tmp[310]; int N,K,M; int cal(int t) { return ((t/10000)-6)*3600+((t%10000)/100)*60+t%100; } int check(int pos,int s,int e) { int rn=0; for(int i=1;i<=Cnt[pos];++i) rn+=(Et[pos][i]==e||(St[pos][i]<s&&Et[pos][i]>e)||(St[pos][i]>s&&Et[pos][i]<e)); return rn; } void print(int t) { printf("ddd\n",6+t/3600,(t%3600)/60,t%60); } int main() { //freopen("data9.in","r",stdin); bool fir=1; while(~scanf("%d%d",&N,&K)) { M=(N-1)*600; if(!fir)puts(""); else fir=0; memset(Cnt,0,sizeof(Cnt)); int i,j,k; int a,b,c; for(i=1;i<=K;++i) { scanf("%d%d%d",&a,&b,&c); if(cal(b)>M)continue; ++Cnt[a]; St[a][Cnt[a]]=cal(b); Et[a][Cnt[a]]=St[a][Cnt[a]]+c; } memset(dp,0x3f,sizeof(dp)); dp[1][0]=0; for(i=1;i<N;++i) { int lt=(i-1)*300;//(i-1)*10*3600/120 int rt=(i-1)*600;;//(i-1)*10*3600/60; for(j=lt;j<=rt;++j) { memset(G,0,sizeof(G)); tmp[0]=dp[i][j]+check(i,j,j+300); for(k=1;k<=Cnt[i];++k)//预处理出G数组 if(j+300<=Et[i][k]&&Et[i][k]<=j+600) { if(St[i][k]<=j)++G[Et[i][k]-j-300][0]; if(St[i][k]>=j)++G[Et[i][k]-j-300][1]; } for(k=300;k<600;++k) if(tmp[k-300]<INF)tmp[k-300+1]=tmp[k-300]+G[k-300+1][1]-G[k-300][0]; for(k=300;k<=600;++k) dp[i+1][j+k]=min(dp[i+1][j+k],tmp[k-300]); } } int lt=(N-1)*300; int rt=(N-1)*600; int ans=INF,best; for(i=rt;i>=lt;--i) { if(ans>=dp[N][i]) { ans=dp[N][i]; best=i; } } printf("%d\n",ans); print(best); } } /* 3 2 1 060000 301 2 060300 600 3 2 1 060000 301 2 060300 600 */