Poj1167 The Buses — 迭代加深DFS+剪枝

Note: 本文最初于 2011年03月10日 星期四 20:08 在 hi.baidu.com/lydrainbowcat 发表。šš

http://poj.org/problem?id=1167

š有一个站台，给定n辆车到站的时刻，时刻在12:00~12:59之间。把这些车分成若干条线路，使得每条线路至少包含2辆车，并且每条线路各次车到站的时间间隔是相等的。求最少的线路数。

š按时间顺序依次考虑每辆车，它只有两种选择，第一是作为某线路的第一辆车，第二是组合到其他线路中去。我们只需要枚举这两种选择。为了线路更少，应该先选择第二种分支。

š我们可以在确定了某线路的第一辆车时，把该线路记录到数组中。以后搜索其它车的时候，尝试与数组中的车组成一条线路，确定时间间隔，然后把该线路需要进出站的时刻都安排好车辆。若可以安排，则把该线路和车辆标记为已处理，搜索下一辆未安排的车；若不能安排，则尝试组成其它线路。注意，每条线路的第一辆车不可能出现在12:30之后的时间。

š题目告诉我们答案一定<=17，因此我们可以迭代加深搜索。

Source Code

Problem: 1167		User: lydliyudong
Memory: 896K		Time: 47MS
Language: Pascal		Result: Accepted

• Source Code

var
 a:array[0..300]of integer;
 b:array[0..60]of integer;
 f:array[0..60]of record color,first:longint; end;
 n,ans,i,j,ID,max:longint;
 flag:boolean;

procedure IDdfs(dep,m:integer);
 var
  i,j,s,e,now,d:longint;
 begin
  if dep>n then
   begin
    for i:=1 to m do//color为1代表是某条线路的第一辆车
     if f[i].color=1 then exit;
    ans:=m;
    flag:=true;
    exit;
   end;
  now:=a[dep];
  if b[now]<=0 then IDdfs(dep+1,m);
  for i:=1 to m do with f[i] do//不当做一条线路的头一辆车
   if color=1 then
    begin
     d:=now-first;//公差
     if d<=first then continue;//注意挖掘深层的隐晦条件，如果d<=first则first-d一定会在输入数据中出现，而我们是把first当做第一辆车处理的，与其矛盾。
     color:=2;
     s:=now;
     while (s<=max)and(b[s]>0) do
      begin
       dec(b[s]);
       inc(s,d);
      end;
    if s>max then IDdfs(dep+1,m);{这里我不得不说理解题意很重要。题目说某一条线路若确定了初始时间和时间间隔，
    则会在整个一小时内均按此规律进站，故线路若中间断开不能延续到12:59之后，就不能算一条线路！}
     if flag then exit;
     color:=1;
     e:=s-d;
     s:=now;
     while s<=e do
      begin
       inc(b[s]);
       inc(s,d);
      end;
    end;
  if (now*2>=59)or(m>=ID) then exit;//每条线路最少两辆车，故now若作为第一辆不会在后一半
  inc(m);
  dec(b[now]);
  with f[m] do
   begin
    color:=1;
    first:=now;
   end;
  IDdfs(dep+1,m);
  if flag then exit;
  inc(b[now]);
 end;

procedure scanf;
 begin
  readln(n);
  for i:=1 to n do
   begin
    read(j);
    if max<j then max:=j;
    inc(b[j]);
    a[i]:=j;
   end;
 end;

begin
 scanf;
 for ID:=1 to 17 do//这题告诉线路<17明摆着让你迭代……
  begin
   IDdfs(1,0);
   if flag then break;
  end;
 writeln(ans);
end.