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。

轉載于:https://www.cnblogs.com/jznoi/p/4171044.html

總結

以上是生活随笔為你收集整理的USACO翻译：USACO 2012 JAN三题（3）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。