UVa1647 Computer Transformation

2014-10-24

链接：Link 耗时：0.679s

分析

本质上，这是一道求数列通项的题目。我们列出前几个字符串： $$01,$$ $$1001,$$ $$01101001,$$ $$1001011001101001,$$ $$\ldots$$

如果用$S_i$表示第 i 个字符串中“00”的个数，则有： $$S_1=0,\ S_2=1,\ S_3=1,\ S_4=3,\ S_5=5,\ S_6=11,\ldots$$

经过观察可以发现有如下规律： $$S_n=2\times S_{n-1}+{(-1)}^n$$

求通项就简单了，换个元即可： $$S_n=\frac{1}{3}[{(-1)}^n+2^{n-1}]$$

程序采用高精度实现。

Code

const
    JINDU = 100000;
var
    n: Integer;
//在数字前补0
procedure PrintANumber(x: longint);
var
    t: longint;
begin
    if x = 0 then
        write('00000')
    else
    begin
        t := JINDU;
        while t > x * 10 do
        begin
            write(0);
            t := t div 10;
        end;
        write(x);
    end;
end;

var
    ans: array [1..300] of longint;
    len, i: integer;
//计算2^(n-1)
procedure calc2;
var
    i, x, t, mul: longint;
begin
    len := 1;
    ans[1] := 1;
    t := n-1;
    while t > 0 do
    begin
        if t < 6 then
            mul := 1 << t
        else
            mul := 64;
        x := 0;
        for i := 1 to len do
        begin
            ans[i] := ans[i] * mul + x;
            x := ans[i] div JINDU;
            ans[i] := ans[i] mod JINDU;
        end;
        if x > 0 then
        begin
            inc(len);
            ans[len] := x;
        end;
        dec(t, 6);
    end;
end;
//除以3
procedure div3;
var
    i, x, t: longint;
begin
    i := len;
    x := 0;
    while i > 0 do
    begin
        t := (x * JINDU + ans[i]);
        ans[i] := t div 3;
        x := t mod 3;
        dec(i);
    end;
    while ans[len] = 0 do dec(len);
end;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    while not eof do
    begin
        readln(n);
        if n=1 then   //特殊情况处理
        begin
            writeln(0);
            continue;
        end;
        fillchar(ans, sizeof(ans), 0);
        calc2;
        if odd(n) then
            dec(ans[1])
        else
            inc(ans[1]);
        div3;
        write(ans[len]);
        for i := len-1 downto 1 do
            PrintANumber(ans[i]);
        writeln;
    end;

    close(input); close(output);
end.

UVa11526 H(n)

2014-10-18

链接：Link 耗时：2.232s

分析

粗看题目，不过就是要求这样一个式子：$\sum_{i=1}^n{[\frac{n}{i}]}$的值。但注意到：题目给的数据范围极大，有$2^{31}-1$之多，若遍历计算，则时间复杂度为$O(n)$，将严重超时，不可取。

而事实上，通过尝试我们可以发现：$\sum_{i=1}^{n}{[\frac{n}{i}]}=2*\sum_{i=1}^{\sqrt n}{[\frac{n}{i}]}-{[\sqrt n]}^2$，这是一个重要的结论。因为这条式子一旦成立，时间复杂度即可从$O(n)$降为$O(\sqrt n)$，这是一个极为可观的改善。下面我们来证明一下这个结论：

事实上，

$$ \begin{aligned} \sum_{i=[{\sqrt n}]+1}^{n}{[\frac{n}{i}]} &=1\times(n-[\frac{n}{2}])+2\times([\frac{n}{2}]-[\frac{n}{3}])+\ldots+[\sqrt{n}]\times([\frac{n}{\sqrt{n}}]-{[\frac{n}{\sqrt n}+1]}) \\ &=n+[\frac{n}{2}]+[\frac{n}{3}]+\ldots+[\frac{n}{\sqrt n}]-[\sqrt n]\times[\frac{n}{[\sqrt n]+1}] \\ &=\sum_{i=1}^{[\sqrt n]}{[\frac{n}{i}]}-{[\sqrt n]}^2 \end{aligned}$$

从而，命题得证。

Code

var
    n, _, i: longint;

function h: int64; inline;
var
    k, t: longint;
begin
    h := 0;
    t := trunc(sqrt(n));
    k := 1;
    while k <=t do
    begin
        h := h + n div k;
        inc(k);
    end;
    h := h * 2 - t * t;
end;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    readln(_);
    while _ > 0 do
    begin
        dec(_);
        readln(n);
        if n <= 0 then
            writeln(0)
        else
            writeln(h);
    end;

    close(input);
    close(output);
end.

UVa817 According to Bartjens

2014-10-17

链接：Link 状态：WA

分析

做了两个小时，很可惜最终还是 WA 了。非常奇怪——和网上的 C++ 代码运行结果完全一样，但却 WA 了。不过，在这里我还是记录一下解题的过程。 这道题数据量很小，直接爆搜每个空位，用 *, +, -, #0 来代表符号或不填。

Code

const
    operators: array [1..4] of char = ('*', '+', '-', #0); //符号
var
    s: string;
    _, n: integer;
    op: array [0..10] of char;
    yes: Boolean;

function toValue(ch: char): integer;
begin
    exit(ord(ch) - ord('0'));
end;

procedure calcAndPrint;
var
    numtop, opstop: Integer;  //数字栈，符号栈
    num: array [1..10] of longint;
    ops: array [1..10] of char;
    i: integer;
begin
    i := 1;
    numtop := 1;
    num[numtop] := toValue(s[1]);
    opstop := 0;
    while i <= n do
    begin
        while (i < n) and (op[i] = #0) do
        begin
            inc(i);
            num[numtop] := num[numtop] * 10 + toValue(s[i]);
        end;
        if (op[i] in ['+', '-']) or (i >= n) then
        begin
            while (opstop > 0) and (ops[opstop] = '*') do
            begin
                dec(opstop);
                num[numtop - 1] := num[numtop] * num[numtop -1];
                dec(numtop);
            end;
        end;
        if i >= n then break;
        inc(opstop);
        ops[opstop] := op[i];
        inc(i);
        inc(numtop);
        num[numtop] := toValue(s[i]);
    end;
    i := 1;
    while i < numtop do
    begin
        if ops[i] = '+' then
            num[i+1] := num[i] + num[i+1]
        else
            num[i+1] := num[i] - num[i+1];
        inc(i);
    end;
    if (num[numtop] = 2000) and (opstop > 0) then
    begin
        yes := True;
        write('  ');
        for i := 1 to n do
        begin
            write(s[i]);
            if op[i] <> #0  then
                write(op[i]);
        end;
        writeln('=');
    end;
end;

procedure dfs(t: integer); //搜索第t个位置
var
    i: Integer;
    ch: char;
begin
    if t = n then
    begin
        calcAndPrint;
        exit;
    end;
    for i := 1 to 4 do
    begin
        ch := operators[i];
        if (ch = #0) and (s[t] = '0') and ((t = 1) or (t > 1) and (op[t-1] <> #0)) then continue;
        op[t] := ch;
        dfs(t+1);
    end;
end;

var
    i: Integer;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    readln(s);
    _ := 0;
    while not eof and (s[1] <> '=') do
    begin
        i := 1;
        while not (s[i] in ['0'..'9', '=']) do
        begin
            inc(i);
        end;
        delete(s, 1, i-1);
        n := pos('=', s) - 1;
        inc(_);
        writeln('Problem ', _);
        yes := False;
        fillchar(op, sizeof(op), 0);
        dfs(1);
        if not yes then
            writeln('  IMPOSSIBLE');
        readln(s);
    end;

    close(input); close(output);
end.

UVa225 Golygons

2014-10-15

链接：Link 耗时：0.699s

思路

dfs(t, x, y, d, s) 表示当前走了 t 步，在 (x,y)，上一个方向为 d，s 为一个求和用的辅助变量。

当前位置无法走完剩下的路时直接回溯。可节省接近 2s 的时间。

p.s. 这道题虽然没有明说每个城市只走一次，但它的确那样判了，这一点坑了我好久。

Code

//Accepted.
const
    dx: array [1..4] of integer = (1, 0, 0, -1);
    dy: array [1..4] of integer = (0, 1, -1, 0);
    dir: array [1..4] of char = ('e', 'n', 's', 'w');

var
    a: array [1..50, 1..2] of integer; //障碍物
    k, i, n, _, x, y: integer;
    ans: array [1..20] of char;
    tot: longint;
    vis: array [-220..220, -220..220] of boolean;

function judge(x1, y1, x2, y2: longint): Boolean; //判断刚刚走过的路上是否有障碍物
var
    i: Integer;
begin
    judge := False;
    if x1 = x2 then
    begin
        for i := 1 to k do
            if (a[i, 1] = x1) and ((a[i, 2] - y1)*(a[i, 2] - y2) <= 0) then exit;
    end
    else
        for i := 1 to k do
            if (a[i, 2] = y2) and ((a[i, 1] - x1)*(a[i, 1] - x2) <= 0) then exit;
    judge := True;
end;

procedure print;
var
    i: Integer;
begin
    for i := 1 to n do write(ans[i]);
    writeln;
    inc(tot);
end;

procedure dfs(t, x, y, d, s: integer);
var
    i, sum: Integer;
    tx, ty: longint;
begin
    if t = n then
    begin
        if (x = 0) and (y = 0) then print;
        exit;
    end;

    sum := s - t - 1;
    inc(t);

    for i := 1 to 4 do
    begin
        if (i = d) or (i + d = 5) then continue;   //方向相同或相反
        tx := x + dx[i] * t;
        ty := y + dy[i] * t;
        if vis[tx, ty] then continue;              //走过
        if abs(tx) + abs(ty) > sum then continue;  //回不去，剪枝
        if not judge(x, y, tx, ty) then continue;  //有障碍物
        ans[t] := dir[i];
        vis[tx, ty] := True;
        dfs(t, tx, ty, i, sum);
        vis[tx, ty] := False;
    end;
end;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    readln(_);
    while _ > 0 do
    begin
        dec(_);
        read(n, k);
        fillchar(vis, sizeof(vis), 0);
        for i := 1 to k do
            read(a[i, 1], a[i, 2]);
        fillchar(ans, sizeof(ans), 0);
        tot := 0;
        dfs(0, 0, 0, -1, n * (n+1) div 2);
        writeln('Found ', tot, ' golygon(s).');
        writeln;
    end;

    close(input); close(output);
end.

UVa12219 Common Subexpression Elimination

2014-10-05

链接：Link 状态：Runtime Error

前言

这题做的可真够久的，整整三个小时。但即便如此，还是只过了一部分的点，另一部分报运行时错误——估计是哈希表设计的不太好。但这确实是一道好题，因此，在睡觉前决定记录一下。

分析

很容易便想到：用一个三元组 $(x,y,z)$ 表示节点，表示内容为 x 的节点下跟着标号为 y 和 z 的左右子树。这样一来，一类相同的子树便可以唯一确定了，而不必每构造一棵子树就把整棵树遍历一遍。 对于三元组的储存，刚开始图方便，用了数组。查找也是用了 $O(n)$ 的线性查找。磕磕碰碰写了两个多小时然后兴冲冲地提交，结果 TLE 了…………没办法，只好又花了半个小时写了一个哈希表，然后就是上文说过的情况了：Runtime Error204。可能是哈希数组过大的原因，日后再微调一下，今天实在是没有脑子了。

Code

const
  maxn = 20000;
type
  NodeRec = record
    Value: string;
    l, r, index: longint;
  end;
  Node = record
      left, right: longint;   //Index of left and right child in the `tree` array, -1 for none.
      Rec: NodeRec;
      index: longint;
  end;
  //以下为哈希表的定义
  _PNode = ^_Node;
  _Node = record
    n: Node;
    next: _PNode;
  end;

  HashTable = object
    arr: array [0..maxn] of _PNode;
    function hash(n: NodeRec): longint;
    procedure add(n: Node);
    procedure clear;
    function find(n: NodeRec): longint;
  end;

procedure HashTable.clear;
var
  i: longint;
  p, q: _PNode;
begin
  for i := 0 to maxn do
  begin
    p := arr[i];
    while p<>nil do
    begin
      q := p^.next;
      dispose(p);
      p := q;
    end;
  end;
  fillchar(arr, sizeof(arr),0);
end;

function cmp(r1, r2: NodeRec): Boolean;
begin
  cmp := (r1.l = r2.l) and (r1.r = r2.r) and (r1.Value = r2.Value);
end;

function HashTable.hash(n: NodeRec): longint;
var
  i: longint;
begin
  hash := 0;
  for i := 1 to length(n.Value) do
    hash := (hash*5 + ord(n.Value[i]) - ord('a')) mod maxn;
  hash := (hash + n.l * 10 + n.r * 5) mod maxn;
end;

procedure HashTable.add(n: Node);
var
  h: longint;
  p, q: _PNode;
begin
  h := hash(n.rec);
  new(q);
  fillchar(q^, sizeof(_Node), 0);
  q^.next := arr[h];
  q^.n := n;
  arr[h] := q;
end;

function HashTable.find(n: NodeRec): longint;
var
  p: _PNode;
begin
  find := -1;
  p := arr[hash(n)];
  while (p<>nil) and not cmp(n, p^.n.rec) do p := p^.next;
  if p <> nil then
    find := p^.n.index;
end;
//哈系表定义结束
var
  inputs: Ansistring;
  _: longint;
  tree: array [1..50001] of Node;
  cur: longint;              //The current pointer of the input string.
  num: longint;              //The current number of the `tree` array.
  ls: longint;
  t: longint;
  tot: longint;
  ht: HashTable;

function build: longint; //建树
label lb;
var
  rec: NodeRec;
  i,j,l,r: longint;
begin
  l := 0;
  r := 0;
  fillchar(rec, sizeof(rec), 0);
  inc(tot);
  rec.index := tot;
  while (cur<=ls) and (inputs[cur] in ['a'..'z']) do
  begin
    rec.Value := rec.Value+inputs[cur];
    inc(cur);
  end;
  if cur>ls then goto lb;    //。。。这里被迫跳转控制流，由于实在不想多谢，就用了臭名昭著的label
  if inputs[cur] = '(' then
  begin
    inc(cur);
    l := build();
    rec.l := tree[l].rec.index;
    inc(cur);
    r := build();
    rec.r := tree[r].rec.index;
    inc(cur);
  end;
  j := ht.find(rec);
  if j>0 then
  begin
    dec(tot);
    exit(j);
  end
  else
  begin
lb:
    inc(num);
    tree[num].left := l;
    tree[num].right := r;
    tree[num].rec := rec;
    tree[num].index := num;
    ht.add(tree[num]);
    exit(num);
  end;
end;

procedure print(n: longint);
begin
  if tree[n].rec.index > t then
  begin
    write(tree[n].rec.Value);
    t := tree[n].rec.index;
  end
  else
  begin
    write(tree[n].rec.index);
    exit;
  end;
  if tree[n].right = 0 then
    exit;
  write('(');
  print(tree[n].left);
  write(',');
  print(tree[n].right);
  write(')');
end;
begin
  assign(input, 'main.in'); reset(input);
  assign(output, 'main.out'); rewrite(output);
  readln(_);
  fillchar(ht.arr, sizeof(ht.arr),0);
  while _>0 do
  begin
    dec(_);
    readln(inputs);
    fillchar(tree, sizeof(tree), 0);
    ht.clear;
    ls := length(inputs);
    cur := 1;  num := 0; tot := 0;
    build;
    t := 0;
    print(num);
    writeln;
  end;
  close(input); close(output);
end.

UVa536 Recovery

2014-10-05

链接：Link 耗时：0.012s

前言

真是疯玩了几天，脑袋都残了，一道弱智题做了近一个小时。

Code

var
    pre, mid, s: string;
    tree: array [1..50] of record
        l, r: integer;
        ch: char;
    end;
    cur: integer;
function init: integer;
var
    m: integer;
begin
    readln(s);
    m := length(s) >> 1 + 1;
    pre := Copy(s, 1, m-1);
    mid := Copy(s, m+1, length(s));
    init := m-1;
end;
function build(l1, l2, r2: integer): integer;
var
    m,len: integer;
    t: integer;
begin
    if l2 > r2 then exit(0); //该子树不存在。**这个地方坑了我很久**
    inc(cur);
    t := cur;      // 这里也坑了我，当下面构造完左右子树后，cur已经变了，所以要缓存起来
    build := t;
    tree[t].ch := pre[l1];
    if r2-l2 = 0 then //叶节点
        exit;
    m := pos(pre[l1], mid); //在中序遍历中找根节点
    len := m - l2;
    tree[t].l := build(l1+1, l2, m-1); //构造左子树
    tree[t].r := build(l1+len+1, m+1, r2); //构造右子树
end;
procedure print(x: integer);
begin
    if x = 0 then exit;
    print(tree[x].l);
    print(tree[x].r);
    write(tree[x].ch);
end;
begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);
    while not eof do
    begin
        fillchar(tree, sizeof(tree), 0);
        cur := 0;
        build(1, 1, init);
        print(1);
        writeln;
    end;
    close(input);
    close(output);
end.

UVa11582 Colossal Fibonacci Numbers! && 大数操作

2014-10-01

链接：Link 耗时：0.139s

前言

这道题的主要思路就是打表，看看 Fibonacci 数列模 n 几个一循环。但由于这题给的数太大了，从而在细节上耗了很久。在此记录一下：

var
    x: qword;
    y: longint;
begin
    x := 1<<64-1;
    y := 100;
    x := x mod y; //报错201
    x := x mod qword(y); //正确
end.

Code

var
    a,b: qword;
    _, n, i, k, cnt: longint;
    f: array [1..1000000] of longint;

function superMod(a, b: qword; m: longint): longint;
var
    x: qword;
begin
    if b = 0 then
        exit(1);
    x := superMod(a, b shr 1, m);
    superMod := x * x mod m;
    if odd(b) then
        superMod := superMod * a mod m;
end;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);
    readln(_);
    while _ > 0 do
    begin
        dec(_);
        readln(a, b, n);
        if a = 0 then
        begin
            writeln(0);
            continue;
        end;
        if n = 1 then
        begin
            writeln(0);
            continue;
        end;
        f[1] := 1;
        f[2] := 1;
        cnt := 2;
        while not ((f[cnt-1] = 1) and (f[cnt] = 0)) do
        begin
            inc(cnt);
            f[cnt] := (f[cnt-1] + f[cnt-2]) mod n;
        end;
        //while x > int64(1 <<60) do
        //    x := x - int64((cnt << 59));
        a := a mod qword(cnt);
        k := superMod(a, b, cnt);
        writeln(f[k]);
    end;
    close(output); close(input);
end.

扩展欧几里得算法

2014-10-01

今天开始学习数论方面的算法。这部分在 NOIP 中并不常出现，即使出现了也不会像高联这么难（。。。）。

什么是扩展欧几里得算法

所谓欧几里得算法，实际上就是辗转相除法——求两个数最大公约数的一种高效算法。而扩展欧几里得算法则是来源于于一类方程的解决：

$$ax+by=gcd(a,b)$$

这有点像是裴蜀定理的一般形式。和裴蜀定理类似，这类方程也有无数多个整数解。如何高效率地求得它的一组特解呢？

代码

procedure gcd_ex(a, b: longint; var d: longint; var x, y: longint);
begin
    if b = 0 then
    begin
        d := a;
        x := 1;
        y := 0;
        exit;
    end;
    // hl:begin #1
    gcd_ex(b, a mod b, d, y, x);
    // hl:end
    y := y-(a div b) * x;
end;

详解

乍一看，算法似乎和一般欧几里得算法很是相似：都是递归实现，参数传递过程中都体现了“辗转相除”的思想。那为什么这个算法是正确的呢？ 这里先解释一下参数：

  • a：方程中的参数 a
  • b：方程中的参数 b
  • d：即 gcd(a,b)。由于和辗转相除法的相似性，在这里最大公约数也可以“顺便”算出。当然，去掉也无大碍
  • (x,y)：方程的一组特解 (x, y)

下面解释标注了 1 的那行代码。

假设方程 $ax+by=gcd(a,b)$ 有一组特解 $(x_0,y_0)$。则有$$ax_0+by_0=gcd(a,b)$$

由最大公约数原理可知：$$gcd(a,b)=gcd(b, a\ mod\ b)$$

从而有$$ax_0+by_0=gcd(b,a\ mod\ b)$$

又方程 $bx+(a\ mod\ b)y=gcd(b,a\ mod\ b)$ 一定有整数解，设其为 $(x_1,y_1)$。则有

$$ax_0+by_0=gcd(b,a\ mod\ b)=bx_1+(a\ mod\ b)y_1$$即$$ax_0+by_0=bx_1+(a-(a\ div\ b)*b)y_1$$

即 $$a(x_0-y_1)=b(x_1-(a\ div\ b)y_1-y_0)$$

由恒等原理可知：$$x_0=y_1$$$$y_0=x_1-(a\ div\ b)y_1$$

因此，当 $a,b\neq0$ 时，$x,y$ 的值可以递归求得。递归边界为：$b=0$ 时 $x=1,y=0$。

注意到上面的算法用到了一个技巧：在递归传参数的时候将 y, x 调换了。这样做的好处是节省了一个中间变量用来储存 $y_1$，否则在计算 $y_0$ 时 $y_1$ 也被覆盖了。从而使算法更加的精简。

应用

  • 计算几何中求整点的问题
  • 求一元一次同余方程 $a\equiv b\pmod{m}$ 的一组特解。（即方程 $ax+my=b$ 的一组特解）

UVa10285 Cake Slicing

2014-10-01

链接：Link 耗时：1.825s

这道题做的可真够久的：前前后后加起来将近有两个小时，因此当 AC 的那一刻，自己心中还是挺自豪的。

事实上，这是一道复杂一点的区间型动态规划，之所以说“复杂”，是因为它的状态转移是二维的：切蛋糕既可以横切，也可以纵切。由此我想到了分治算法：

假设一个矩形它所需要切的刀数是 f，则 f 可以由组成该矩形的小矩形的 f 值决定。

因此，这个问题具有最优子结构。由于每个状态为一个矩形，因此需要 4 个维度来记录状态（及左上、右下两个顶点）。下面是横切时的状态转移方程，纵切时同理可得：

$$ \begin{aligned} f(up, down, left, right) = &\ min\{f(up, i, left, right) \\ & + f(i, down, left, right) + right - left\},i = up + 1 .. down -1 \end{aligned} $$

{$R-}
const INF = maxint div 5; //正无穷
var
    f: array [0..20, 0..20, 0..20, 0..20] of integer;
    cherries: array [1..500, 1..2] of integer;
    map: array [0..20, 0..20] of boolean;
    n, m, i, k: integer;

function min(x, y: integer): integer; inline;
begin
    if x<y then exit(x) else exit(y);
end;

function cherryin(u, d, l, r: integer): integer; inline; //判断矩形内有没有樱桃
var
    i, j: integer;
begin
    cherryin := 0;
    for i := u+1 to d do
        for j := l+1 to r do
            if map[i, j] then
            begin
                inc(cherryin);
                if cherryin = 2 then exit;
            end;
end;

function dp(u, d, l, r: integer): integer;
var
    b: integer;
    i: integer;
begin
    if f[u, d, l, r] <> -1 then
        exit(f[u,d , l, r]);
    b := cherryin(u, d, l, r);
    if b = 1 then
    begin
        f[u, d, l, r] := 0;
        exit(0);
    end;
    if b = 0 then
    begin
        f[u, d, l, r] := INF;
        exit(INF);
    end;
    dp := INF;
    for i := u+1 to d-1 do
        dp := min(dp, dp(u, i, l, r)+dp(i, d, l, r)+r-l);
    for i := l+1 to r-1 do
        dp := min(dp, dp(u, d, l, i)+dp(u, d, i, r)+d-u);
    f[u, d, l, r] := dp;
end;

var
    _: integer;

begin
    assign(input, 'main.in');reset(input);
    assign(output, 'main.out');rewrite(output);
    _ := 0;
    readln(n, m, k);
    while n>0 do
    begin
        inc(_);
        fillchar(map, sizeof(map), 0);
        fillchar(f, sizeof(f), -1);
        for i := 1 to k do
        begin
            readln(cherries[i, 1], cherries[i, 2]);
            map[cherries[i, 1], cherries[i, 2]] := true;
        end;
        writeln('Case ',_,': ', dp(0,n,0,m));
        readln(n, m, k);
    end;
    close(input);close(output);
end.

UVa10285 Longest Run on a Snowboard

2014-09-29

链接：Link 耗时：0.028s

一道简单的动态规划，主要思路就是：用 $f[i,j]$ 表示到达 $(i,j)$ 的最长路径的长度。找到每个最高点，从其开始向四周的低处搜索。如果该点已搜过并且 f 值大于当前长度则退出回溯。直到达到某个最低点为止。

不多说了，直接上代码：

const
    delta :array [1..4, 1..2] of integer = ((-1, 0), (1, 0), (0, 1), (0, -1)); //四个方向向量
var
    _: Integer;
    name: string;
    n, m, i, j, x: Integer;
    ans: longint;
    map: array [0..101, 0..101] of integer;
    f: array [1..100, 1..100] of longint;

function max(x, y: longint): longint; inline;
begin
    if x>y then exit(x) else exit(y);
end;

function can(x, y: integer): Boolean; inline; //判断是否是最高点
var
    i: Integer;
    tx, ty: integer;
begin
    can := true;
    for i := 1 to 4 do
    begin
        tx := x + delta[i, 1];
        ty := y + delta[i, 2];
        can := can and (map[x, y] >= map[tx, ty]);
        if not can then break;
    end;
end;

procedure dp(x, y: integer; len: longint); //回溯进行动态规划
var
    i: Integer;
    tx, ty: integer;
begin
    inc(len);
    if f[x, y] > len then exit;
    f[x, y] := len;
    ans := max(ans, len);
    for i := 1 to 4 do
    begin
        tx := delta[i, 1] + x;
        ty := delta[i, 2] + y;
        if (tx = 0) or (tx > n) or (ty = 0) or (ty > m) then continue;
        if map[x, y] <= map[tx, ty] then continue;
        dp(tx, ty, len);
    end;
end;

procedure ReadAndProcessName; //处理那行该死的名字！！
var
    s: string;
    i: integer;
begin
    readln(s);
    i := 1;
    name := '';
    n := 0;
    m := 0;
    while s[i] <> ' ' do
    begin
        name := name + s[i];
        inc(i);
    end;
    inc(i);
    while s[i] <> ' ' do
    begin
        n := n * 10 + ord(s[i]) - ord('0');
        inc(i);
    end;
    inc(i);
    while i <= length(s) do
    begin
        m := m * 10 + ord(s[i]) - ord('0');
        inc(i);
    end;
end;

begin
    assign(input, 'main.in');reset(input);
    assign(output, 'main.out');rewrite(output);
    readln(_);
    while _>0 do
    begin
        dec(_);
        fillchar(map, sizeof(map), 0);
        ReadAndProcessName;

        for i := 1 to n do
            for j := 1 to m do
            begin
                read(x);
                map[i, j] := x+1;
            end;
        readln;

        fillchar(f, sizeof(f), 0);
        ans := 0;
        for i := 1 to n do
            for j := 1 to m do
                if can(i, j) then
                    dp(i, j, 0);
        writeln(name, ': ', ans);
    end;
    close(input);close(output);
end.
上一页
© hsfzxjy 的博客. Powered by Hexo. Theme by hsfzxjy.
粤公网安备44011202001249号粤ICP备2020075702号-1