USACO 2012JAN（题目三）

一、题目概览

二、运行内存限制

1.放牧{Bronze题3}

【问题描述】

    FJ的牧场是一个5X5的正方形，每个格子的大小是1X1,左上角是(1,1)，右下角是（5,5）。

(1,1) (1,2) (1,3) (1,4) (1,5)

(2,1) (2,2) (2,3) (2,4) (2,5)

(3,1) (3,2) (3,3) (3,4) (3,5)

(4,1) (4,2) (4,3) (4,4) (4,5)

(5,1) (5,2) (5,3) (5,4) (5,5)

除了K个(0 <= K <= 22, K为偶数)格子，其他的每个格子都有牧草。贝牛从（1,1）开始放牧，米牛从（5,5）开始放牧，则两个格子确保有牧场。

每半个小时，贝牛和米牛都会吃完他们各自所在格子里面的草，然后走到相邻的格子里。他们想吃完所有的牧场，而且结束的时候在同一个位置。请计算一共有多少种方案。贝牛和米牛每次都走到有草的格子，而且他们不会同时走到同一个格子，除非当前格子是最后一个有草的格子。

【文件输入】

    第一行，一整数K。

    第2..K+1行，每行两个整数，表示一个没有草的格子的行号和列号。

【文件输出】

    一行，一个整数，表示方案数。

【输入样例】

4

3 2

3 3

3 4

3 1

输入说明：

b  .  .  .  .

.  .  .  .  .

x  x  x  x  .

.  .  .  .  .

.  .  .  .  m

【输出样例】

1

【样例说明】

b  b--b  b--b

|  |  |  |  |

b--b  b--b  b

             |

x  x  x  x b/m

              |

m--m--m--m--m

|

m--m--m--m--m

2. 登山{silver题3}

【问题描述】

    FJ的准备让他的N(1 <= N <= 25,000)头年登山并下山。第i头牛需要U(i)的时间登山，D(i)的时间下山。每头牛上山和下山都需必须要一个农夫引导。现在有两个农夫FJ（负责上山引导）和他的表哥FD（负责下山引导），在每个时间点，最多有一头牛在登山，一头牛在下山。一群牛可能会聚集在山顶等待FD的引导，牛群上山的顺序和下山的顺序可能不同。

    请计算整个登山活动（所有牛上山并下山）的最少时间花费。

【文件输入】

    第一行，一个整数N，表示牛的数量。

    第2..N+1行，每行两个整数U(i)和 D(i)。(1 <= U(i), D(i) <= 50,000).

【文件输出】

    一行，一个整数，表示最小时间花费。

【输入样例】

3

6 4

8 1

2 3

【输出样例】

17

【样例说明】

上山顺序为3,1,2，下山顺序也是3,1,2。

USACO翻译：USACO 2012 JAN三题（3）