USACO open10金组铜组中文试题

USACO open10试题

金组试题

Problem 1: 奶牛的跳格子游戏[John Pardon, 2010]

奶牛们正在回味童年，玩一个类似跳格子的游戏，在这个游戏里，奶牛们在

草地上画了一行N个格子，(3 <=N <= 250,000)，编号为

1..N。

就像任何一个好游戏一样，这样的跳格子游戏也有奖

励！第i个格子标有一个数字V_i(-2,000,000,000 <=V_i

<= 2,000,000,000)表示这个格子的钱。奶牛们想看看最

后谁能得到最多的钱。

规则很简单：

* 每个奶牛从0号格子出发。(0号格子在1号之前，

那里没钱)

* 她向N号格子进行一系列的跳跃(也可以不跳)，每

次她跳到的格子最多可以和前一个落脚的格子差K格(1

<= K <= N)(比方说，当前在1号格，K=2, 可以跳到2号和3号格子)

*在任何时候，她都可以选择回头往0号格子跳，直到跳到0号格子。另外，除了以上规则之外，

回头跳的时候还有两条规则：

*不可以跳到之前停留的格子。

*除了0号格子之外，她在回来的时候，停留的格子必须是恰巧过去的时候停留的某个格子的前一格(当然，也可以跳过某些过去时候停留的格子)。简单点说，如果i号格子是回来停留的格子，i+1号就必须是过去停留的格子，如果i+1号格子是过去停留的格子，i号格子不一定要是回来停留的格子。(如果这里不太清楚的可以去看英文原文)

她得到的钱就是所有停留过的格子中的数字的和，请你求出最多奶牛可以得到的钱数。

在样例中，K=2，一行5个格子。

格子 编号: 0 1 2 3 4 5

+---+ +---+ +---+ +---+ +---+ +---+

|///|--| |--| |--| |--| |--| |

+---+ +---+ +---+ +---+ +---+ +---+

钱数 : - 0 1 2 -3 4

一个合法的序列Bessie可以选择的是0[0], 1[0], 3[2], 2[1], 0[0]。(括号里的数表示钱数)这样，可以得到的钱数为0+0+2+1+0 = 3。

如果Bessie选择一个序列开头为0, 1, 2, 3, ...，那么她就没办法跳回去了，因为她没办法再跳到一个之前没跳过的格子。

序列0[0], 2[1], 4[-3], 5[4], 3[2], 1[0], 0[0]是最大化钱数的序列之一，最后的钱数为(0+1-3+4+2+0 = 4)。

PROBLEM NAME: hop

INPUT FORMAT:

* 第1行 1: 两个用空格隔开的整数: N 和 K

* 第2到N+1行: 第i+1行有一个整数

: V_i

USACO open10金组铜组中文试题

SAMPLE INPUT (file hop.in):

5 2

1

2

-3

4

OUTPUT FORMAT:

* 第一行: 一个单个的整数表示最大的钱数是多少。

SAMPLE OUTPUT (file hop.out):

4

OUTPUT DETAILS:

还有一种可能的最大化钱数的序列是: 0 2 4 5 3 1 0

********************************************************************* Problem 2: 冲浪 [John Pardon, 2010]

受到秘鲁的马丘比丘的新式水上乐园的启发，Farmer John决定也为奶牛们建一个水上乐园。当然，它最大的亮点就是新奇巨大的水上冲浪。

超级轨道包含 E (1 <= E <=150,000)条小轨道连接

着V (V <= 50,000)个水池，编号为1..V。每个小轨道必

须按照特定的方向运行，不能够反向运行。奶牛们从1

号水池出发，经过若干条小轨道，最终到达V号水池。每

个水池(除了V号和1号之外，都有至少一条小轨道进来

和一条小轨道出去，并且，一头奶牛从任何一个水池到达

V号水池。最后，由于这是一个冲浪，从任何一个水池出

发都不可能回到这个水池)

每条小轨道从水池P_i到水池Q_i (1 <= P_i <= V;

1<= Q_i <= V; P_i != Q_i)，轨道有一个开心值F_i (0

<= F_i <= 2,000,000,000)，Bessie总的开心值就是经

过的所有轨道的开心值之和。

Bessie自然希望越开心越好，并且，她有足够长的时间在轨道上玩。因此，她精心地挑选路线。但是，由于她是头奶牛，所以，会有至多K (1 <= K <= 10)次的情况，她无法控制，并且随机从某个水池选择了一条轨道(这种情况甚至会在1号水池发生)

如果Bessie选择了在最坏情况下，最大化她的开心值，那么，她在这种情况下一次冲浪可以得到的最大开心值是多少？

在样例中，考虑一个超级轨道，包含了3个水池(在图中用括号表示)和4条小轨道，K的值为1

(开心值在括号外表示出来，用箭头标识)

[1]

/ \

5 -> / \ <- 9

/ \ [2]---3---[3]

USACO open10金组铜组中文试题

\__5__/

她总是从1号水池出发，抵达3号水池。如果她总是可以自己选择，就是不会发生不能控制的情况她可以选择从1到2(这条轨道开心值为5)，再从2到3(开心值为5)，总的开心值为5+5=10。但是，如过她在1号水池失去控制，直接到了3，那么开心值为9，如果她在2号水池失去控制，她总的开心值为8。 Bessie想要找到最大化开心值的方案，可以直接从1到3，这样，如果在1号水池失去控制，这样，她就不会在2号水池失去控制了，就能够得到10的开心值。因此，她的开心值至少为9

PROBLEM NAME: slide

INPUT FORMAT:

* 第一行: 三个用空格隔开的整数: V, E, 和 K

* 第2到第E+1行: 第i+1行包含三个用空格隔开的整数:

P_i, Q_i, and F_i

SAMPLE INPUT (file slide.in):

3 4 1

2 3 5

1 2 5

1 3 9

2 3 3

OUTPUT FORMAT:

* 第一样: 一行一个整 …… 此处隐藏：6654字，全部文档内容请下载后查看。喜欢就下载吧 ……