首页 > 代码库 > USACO翻译：USACO 2012 JAN三题（3）
USACO翻译：USACO 2012 JAN三题（3）
USACO 2012JAN（题目三）
一、题目概览
中文题目名称 | 放牧 | 登山 | 奶牛排队 |
英文题目名称 | grazing | climb | lineup |
可执行文件名 | grazing | climb | lineup |
输入文件名 | grazing.in | climb.in | lineup.in |
输出文件名 | grazing.out | climb.out | lineup.out |
每个测试点时限 | 1秒 | 1秒 | 1秒 |
测试点数目 | 10 | 10 | 10 |
每个测试点分值 | 10 | 10 | 10 |
比较方式 | 全文比较 | 全文比较 | 全文比较 |
二、运行内存限制
运行内存上限 | 128 M | 128 M | 128 M |
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）