骨牌遊戲

題目敘述

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

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

輸入說明

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

n w
s1 s2 ... sn

也許會有很多組,讀到w和n都是0的時候結束,不需對這一組做輸出 (w和n和s1,s2 ... sn都為小於1001的正整數)

輸出說明

min

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

範例輸入

3 1 
2 3 5 
0 0

範例輸出

提示

由於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

Source

TIOJ 1432

Judge Setting

run-time limit: 1000 ms
memory limit: 655360 byte
測資數量: 0