1322 問(wèn)題 G: 沙子合并
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 269 解決: 124
題目描述
設(shè)有N堆沙子排成一排，其編號(hào)為1，2，3，…，N（N< =300）。每堆沙子有一定的數(shù)量，可以用一個(gè)整數(shù)來(lái)描述，現(xiàn)在要將這N堆沙子合并成為一堆，每次只能合并相鄰的兩堆，合并的代價(jià)為這兩堆沙子的數(shù)量之和，合并后與這兩堆沙子相鄰的沙子將和新堆相鄰，合并時(shí)由于選擇的順序不同，合并的總代價(jià)也不相同，如有4堆沙子分別為 1 3 5 2 我們可以先合并1、2堆，代價(jià)為4，得到4 5 2 又合并 1，2堆，代價(jià)為9，得到9 2 ，再合并得到11，總代價(jià)為4+9+11=24，如果第二步是先合并2，3堆，則代價(jià)為7，得到4 7，最后一次合并代價(jià)為11，總代價(jià)為4+7+11=22；問(wèn)題是：找出一種合理的方法，使總的代價(jià)最小。輸出最小代價(jià)。
輸入
第一行一個(gè)數(shù)N表示沙子的堆數(shù)N。
第二行N個(gè)數(shù)，表示每堆沙子的質(zhì)量。 < =1000
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情