jzoj 1402. 【2012.03.09普及组】旅行

发布于 2019-03-22  5 次阅读


 

题目描述

你要进行一个行程为7000KM的旅行,现在沿途有些汽车旅馆,为了安全起见,每天晚上都不开车,住在汽车旅馆,你手里现在已经有一个旅馆列表,用离起点的距离来标识,如下:

0, 990, 1010, 1970, 2030, 2940, 3060, 3930, 4060, 4970, 5030, 5990, 6010, 7000

但在出发之前可能还要增加一些旅馆。

现在旅行社为了节约成本要求每天至少行驶A公里,国家旅行社为了安全起见要求每天最多只能行驶B公里。

你想知道一共有多少种旅行方案。

 

输入

    第一行输入A,第二行输入B,第三行输入N(0<=N<=20),表示在出发之前又新增N个汽车旅馆,接下来N行,每行一个整数m,表示旅馆离起点的距离(0

输出

    输出一共有多少种旅行方案。

 

我用了搜索,就是找每一次可以走到的点,走到终点就加一

var
  f,o:array[0..10000] of longint;
  i,j,k,n,m,s,a,b,x,y:longint;

procedure dfs(x:longint);
var
  i,j,k:longint;
begin
  if x=y then begin inc(s); exit; end;
  for i:=x+1 to y do
    if (f[i]-f[x]<=b) and (f[i]-f[x]>=a) then
      dfs(i);
end;

begin
  f[1]:=990;
  f[2]:=1010;
  f[3]:=1970;
  f[4]:=2030;
  f[5]:=2940;
  f[6]:=3060;
  f[7]:=3930;
  f[8]:=4060;
  f[9]:=4970;
  f[10]:=5030;
  f[11]:=5990;
  f[12]:=6010;
  f[13]:=7000;
  readln(a);
  readln(b);
  readln(n);
  for i:=1 to n do
    begin
      readln(x);
      f[13+i]:=x;
    end;
  y:=13+n;
  for j:=1 to y do
    for k:=1 to y-1 do
      begin
        if f[k]>f[k+1] then
          begin
          x:=f[k];
          f[k]:=f[k+1];
          f[k+1]:=x;
          end;
      end;

  dfs(0);
  writeln(s);
end.

 

]]>


「墨泼三千烟火,许你一世迷离」