1432 . 骨牌遊戲
TopCoder
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
2 3 5
0 0
Sample Output 1
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 |