TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

91.9% (125/136)

Submission's AC Ratio

36.2% (262/724)

Tags

Description

骨牌是一片片長方形的塑膠牌,可以將它立起來排成你想要的圖案,加上骨牌本身會有顏色的變化,所以在壓下骨牌後,骨牌一塊塊倒下,就可以展現出美麗的圖案。但是在排骨牌的過程中,常常會有不小心壓到的時候,導致辛苦的結果都不見了。所以有人發明了一種很重的骨牌,在必要的地方把關,防止在你不小心壓下骨牌後,造成的結果會很慘,因為它有足夠的重量,不會倒下,讓傷害停在這裡。

然而我們所擁有的很重骨牌只有幾個,只能在真的非常重要的地方把關,每一個地方會用一個正整數(cost)表示,定義為它排好所需的時間,需要越長,代表重排也要越久,也就越重要。於是我們必須善用這些很重的骨牌,讓傷害降到最小,我們將最大傷害強度定義為,碰倒任一張骨牌之後(可能向前倒或向後倒),可能需要重排的 cost 總和的最大值。

Input Format

$w$ 個很重的骨牌,$n$ 條排好的骨牌列,每一列的 cost 按照順序排好,形式如下

$n \ w$
$s_1 \ s_2 \cdots s_n$

也許會有很多組,讀到 $w$ 和 $n$ 都是 $0$ 的時候結束,不需對這一組做輸出。
($w, n$ 和 $s_1, s_2 \cdots s_n$ 都為小於 $1001$ 的正整數)

Output Format

min

min 為在你安排好很重骨牌的位置後,讓最大傷害強度降到最低的值

Sample Input 1

3 1
2 3 5
0 0

Sample Output 1

5

Hints

由於 3 1 那一組可以將一個很重的骨牌放在 2 前、2 3間、3 5間、5後,其中2前的最大傷害強度為 10,2 3 間的最大傷害強度為 8,3 5 間的最大傷害強度為 5,5後的最大傷害強度為 10,所以把重骨牌放在 3 5 間做保護會得到最好的結果min(10,8,5,10)=5,因此最後 min 為 5

Problem Source

原TIOJ1432 / NPSC2004初賽(prob B)
2021.02.15 Update: Added $\LaTeX$ by FHVirus

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1