[问题描述]
　　在一条没有分岔的公路上有n个距离相等的关口，车只能在关口改变速度。有m辆巡逻车分别在时刻从第个关口出发，匀速行驶到达第+1个关口，耗费时间为秒。求一辆于6点整从第1个关口出发去第n个关口的车最少会与多少辆巡逻车相遇，以及在此情况下到达第n个关口的最早时刻。

[问题分析]
　　本题用动态规划解。
　　设D(x, t)表示在时刻t到达第x个关口的途中最少已与巡逻车相遇的次数。则状态转移方程为：
　　
　　边界条件D(1, 6 3600) = 0
　　问题的解
　　其中， 是计算目标车于时刻t-Δt从第x-1个关口出发，于时刻t到达第i个关口，途中与巡逻车相遇的次数。

[函数w的计算]
　　先对巡逻车按出发的关口排序，重新对这些巡逻车进行编号。用p[x]记下出发站在第x个关口的巡逻车的最小编号，这样在对状态F(x, t)转移时，只要考虑编号从p[x-1]到p[x]-1的巡逻车。
　　计算 时，对于每辆从第x个关口出发的编号为k的巡逻车，设其出发时刻和到达时刻分别为和 ，则：
　　若，则目标车与该巡逻车同时到达；
　　若，则目标车超过巡逻车；
　　若，则巡逻车超过目标车。
　　满足上述情况任意的一种，该巡逻车和目标车相遇。
　　综上，设表示目标车与编号为k的巡逻车从时刻到是否相遇，则
(很显然，对于不同的巡逻车至多只相遇1次)
所以，

[优化措施]
　　对于D(x, t)，t受到x的约束：300(x - 1) + 6 3600 ≤ t ≤ 600(x - 1) + 6 3600。所以，t ≤ 600(n - 1) - 300(n - 1) ≤ 14400。所以对于每层D(x)，只要一个[0..14400]的数组，这里D(x, i)相当于D(x, 300(x - 1) + 6 3600 + i)。注意到D(x, t)只继承上一层的内容，在具体编程时只要开两层数组就够了。
这样，空间完全可以接受。

[小结]
　　该题的动态规划的想法并不难，但是按上述方法程序的速度仍不很乐观。
　　计算一下复杂度：
　　阶段一共n层，第k层有300(k-1)个状态，每个状态决策300次，一共45000n(n-1)次决策。每次决策要计算一次w函数，假设巡逻车平均分布即每个站有6个巡逻车，总的复杂度是45000n(n-1) 6 = 661,500,000。
这样的复杂度还是很高，有待进一步的改进。

[参考程序]

{$R-,Q-}
const
　FileIn = 'patrol.i10';
　FileOut = 'patrol.out';
type
　tCar = record
　　　　　start, stop : longint;
　　　　end;
var
　d : array[1..2, 0..15100]of word;
　Cars : array[1..300]of tCar;
　Point : array[1..51]of word;
　N, M : Word;
　min, max : Longint;
　time : longint;
　p1, p2 : byte;

function TimeToSec(s : string) : longint;
var code : integer;
　p, q : longint;
begin
　val(s[1] + s[2], q, code);
　p := q * 3600;
　val(s[3] + s[4], q, code);
　p := p + q * 60;
　val(s[5] + s[6], q, code);
　p := p + q;
　timetosec := p;
end;

procedure ReadData;
var F : text;
　i : word;
　j, k : byte;
　s : string;
　ch : char;
　spend : longint;
begin
　assign(f, filein); reset(f);
　readln(f, n, m);
　for i := 1 to m do
　begin
　　read(f, k);
　　read(f, ch); while ch = ' ' do read(f, ch);
　　s := ch; for j := 1 to 5 do begin read(f, ch); s := s + ch; end;
　　cars[i].start := TimeToSec(s);
　　readln(f, spend);
　　cars[i].stop := cars[i].start + spend;
　　if point[k] = 0 then point[k] := i;
　end;
　close(f);
　point[n + 1] := m + 1;
　for i := n downto 1 do
　　if point[i] = 0 then point[i] := point[i + 1];
end;

procedure Dynamic;
var current, curr2, pp : word;
　i, j, k : integer;
　t1, t2 : Longint;
begin
　min := 6 * 3600;
　max := min;
　p2 := 1; p1 := 2;
　d[p1, 0] := 0;
　for pp := 1 to n - 1 do
　begin
　　p1 := p2; p2 := 3 - p2;
　　inc(min, 300); inc(max, 600);
　　curr2 := 65535;
　　for i := 0 to max - min do
　　begin
　　　d[p2, i] := 65535;
　　　t2 := i + min;
　　　for j := 300 to 600 do
　　　if (i + 300 - j >= 0) and (i + 300 - j <= max - min - 300) then
　　　begin
　　　　current := d[p1, i + 300 - j];
　　　　t1 := t2 - j;
　　　　for k := point[pp] to point[pp + 1] - 1 do
　　　　　with cars[k] do
　　　　　 　if (stop = t2) or
　　　　　　　　(start < t1) and (stop > t2) or
　　　　　　　　(start > t1) and (stop < t2) then inc(current);
　　　　if current < d[p2, i] then
　　　　begin
　　　　　d[p2, i] := current;
{　　　　if current = curr2 then break; }
　　　　if current < curr2 then curr2 := current;
　　　　end;
　　　end;
　　end;
　end;
end;

function SecToTime(d : longint) : string;
var n1, n2, n3 : byte;
　s1, s2, s3 : string[2];
begin
　n1 := d div 3600;
　d := d mod 3600;
　n2 := d div 60;
　n3 := d mod 60;
　str(n1, s1);
　if length(s1) = 1 then s1 := '0' + s1;
　str(n2, s2);
　if length(s2) = 1 then s2 := '0' + s2;
　str(n3, s3);
　if length(s3) = 1 then s3 := '0' + s3;
　SecToTime := s1 + s2 + s3;
end;

procedure Out;
var F : text;
　i, j, mi : word;
　tt : longint;
begin
　assign(f, fileout); rewrite(f);
　mi := 65535;
　for i := 0 to max - min do
　　if d[p2, i] < mi then
　　begin
　　　mi := d[p2, i];
　　　j := i;
　　end;
　writeln(f, mi);
　writeln(f, SecToTime(j + min));
　close(F);
end;

begin
　time := meml[$40:$6c];
　ReadData;
　Dynamic;
　Out;
　writeln((meml[$40:$6c] - time) / 18.2 : 0 : 2)
end.