題目描述

給出一個數(shù)列，每次會從數(shù)列中挑選出一個數(shù)字，但規(guī)則是每次只能選和0相鄰的數(shù)字（不能選0），拿走一個數(shù)字后，將這個數(shù)字變成0。 現(xiàn)有兩個玩家都采取最優(yōu)策略，使自己最后獲得數(shù)字的和為最大值，輸出最后兩位玩家的得分，優(yōu)勝者將獲得參觀航天發(fā)射基地的門票。保證這個數(shù)列初始時至少有一個數(shù)字為0。

輸入說明

第一行，一個正整數(shù)N(N < 1000000) 。第二行為N個整數(shù)，用一個空格分隔，N個整數(shù)和不超過2^64-1。

輸出說明

輸出數(shù)據(jù)是一行，包括兩個整數(shù)，用一個空格分隔，表示兩人最后的得分。

輸入樣例

8

1 2 0 3 7 4 0 9

輸出樣例

17 9

本題 只討論讓選手得到盡量多的石子。

由于雙方最終石子數(shù)之和是確定的,雙方的目標就是使自己-別人的石子數(shù)差最大化。

首先我們可以抽象問題:

有兩個棧,若干個雙頭隊列,總長度不超過10^6

每次可以從棧頂取一個數(shù),也可以從雙頭隊列選一端取一個數(shù)。

2人輪流以最大化自己數(shù)字和的目標取數(shù),問最終結(jié)果。

如果只有一個棧,那么取法是一定的。

如果只有一個隊列,如果是奇數(shù)個數(shù)據(jù),取法也是一定的。如果是偶數(shù)個,先手會取

max(奇數(shù)位的和,偶數(shù)位的和).

本題的關(guān)鍵難點是將原始數(shù)據(jù)簡化成類似下面的數(shù)據(jù)。即可取元素都是遞減的,比如

1 2 3 0 2 1 2 0 4 1

這里：中間沒有凸狀數(shù)據(jù)，兩頭沒有凹狀數(shù)據(jù)，類似

1<2,? ?4>1.

容易發(fā)現(xiàn)先手只要貪心地從能取的元素里面揀最大的取走即可。由于每次一定可以取全場最大值,所以只要一次排序然后交替取值即可。

4 3 2 2 2 1 1 1

如果中間有凸狀數(shù)據(jù)，或者兩頭有凹狀數(shù)據(jù),我們可以通過 2 個操作來化簡數(shù)列:

1. 如果兩頭有凹狀數(shù)據(jù)，即最左端是 A B.. 或者最右端是..B A, 且 A>=B，

那么雙方在有其它方案時都不會愿意先取走 B,故這種情況可以留到博弈的最后。

由于石子數(shù)是確定的,可以直接推出最后誰取到了 A,算出相應(yīng)差值。

由于可以留到游戲的最后,此時刪除這兩堆并不影響兩人之前的決策。

2. 如果中間有凸狀數(shù)據(jù)，即有一段 ..A B C.. 且滿足 B>=A B>=C，那么我們直接把 ABC 替換成一個 A+C-B 即可。

我們可以這樣想:選 A,B,C 的時候是因為沒有更好的決策而被迫選的。事實上當全場沒有大于 A+C-B 的石子堆可以直接取時,才會考慮取 A,C 中的一個。那么不管第一次取 A,B,C 中的元素是從哪邊,

后手選 B>A(C) 一定是最好的選項。 故先手一定取走 A+C,后手取走 B。從對分數(shù)差的貢獻來看,我們可以直接把 A,B,C 代替成 A+C-B