练习题 - 船(动态规划)

前言

算法拾遗继续。

题目

问题描述

PALMIA国家被一条河流分成南北两岸,南北两岸上各有N个村庄。北岸的每一个村庄有一个唯一的朋友在南岸,且他们的朋友村庄彼此不同。
每一对朋友村庄想要一条船来连接他们,他们向政府提出申请以获得批准。由于河面上常常有雾,政府决定禁止船只航线相交(如果相交,则很可能导致碰船)。

你的任务是编写一个程序,帮助政府官员决定批准哪些船只航线,使得不相交的航线数目最大。

输入(ships.in)

输入文件由几组数据组成。每组数据的第一行有2个整数X,Y,中间有一个空格隔开,X代表PALMIA河的长度(10<=X<=6000),Y代表河的宽度(10<=Y<=100)。第二行包含整数N,表示分别坐落在南北两岸上的村庄的数目(1<=N<=5000)。在接下来的N行中,每一行有两个非负整数C,D,由一个空格隔开,分别表示这一对朋友村庄沿河岸与PALMIA河最西边界的距离(C代表北岸的村庄,D代表南岸的村庄),不存在同岸又同位置的村庄。最后一组数据的下面仅有一行,是两个0,也被一空格隔开。

输出(ships.out)

对输入文件的每一组数据,输出文件应在连续的行中表示出最大可能满足上述条件的航线的数目。

样例

ships.in

30 4
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
0 0

ships.out

4

解答

具体代码实现如下。

#include <stdio.h>

FILE *in, *out;
int ship[5001][2], n, x, y, ans[5001] = {0};

void kuaipai(int first, int end) {
  int tem1, tem2, i = first, j = end;
  if (first < end) {
    tem1 = ship[first][0], tem2 = ship[first][1];
    do {
      while (j > i && ship[j][0] >= tem1)
        j--;
      if (j > i) {
        ship[i][0] = ship[j][0];
        ship[i][1] = ship[j][1];
        i++;
      }
      while (j > i && ship[i][0] < tem1)
        i++;
      if (j > i) {
        ship[j][0] = ship[i][0];
        ship[j][1] = ship[i][1];
        j--;
      }
    } while (j > i);
    ship[i][0] = tem1;
    ship[i][1] = tem2;
    kuaipai(first, i - 1);
    kuaipai(i + 1, end);
  }
}

int main() {
  int i, j, k, t, end;

  in = fopen("ships.in", "r");
  out = fopen("ships.out", "w");

  // since simple data contains only one case, for simplicity, the following assumes there is only one case 
  fscanf(in, "%d%d", &x, &y);
  fscanf(in, "%d", &n);
  for (i = 1; i <= n; i++)
    fscanf(in, "%d%d", &ship[i][0], &ship[i][1]);

  kuaipai(1, n);

  ans[1] = ship[1][1];
  end = 1;
  for (k = 2; k <= n; k++) {
    i = 0;
    j = end + 1;
    t = (i + j) / 2;
    while (j - i > 1) {
      if (ship[k][1] >= ans[t]) {
        i = t;
        t = (i + j) / 2;
      } else {
        j = t;
        t = (i + j) / 2;
      }
    }
    ans[j] = ship[k][1];
    if (j > end)
      end = j;
  }

  fprintf(out, "%d\n", end);

  fclose(in);
  fclose(out);

  return 0;
}

后记

因为最近有特殊事情要忙,所以以上仅贴出以前的代码,未经我自己重新理解与校验,当然也有计划在以后重新完善当前文章。

参考


* cached version, generated at 2018-12-02 17:58:56 UTC.

Subscribe by RSS