設有N堆沙子排成一排，其編號為1，2，3，…，N（N< =300）。每堆沙子有一定的數(shù)量，可以用一個整數(shù)來描述，現(xiàn)在要將這N堆沙子合并成為一堆，每次只能合并相鄰的兩堆，合并的代價為這兩堆沙子的數(shù)量之和，合并后與這兩堆沙子相鄰的沙子將和新堆相鄰，合并時由于選擇的順序不同，合并的總代價也不相同，如有4堆沙子分別為  1    3    5    2  我們可以先合并1、2堆，代價為4，得到4  5  2  又合并  1，2堆，代價為9，得到9  2  ，再合并得到11，總代價為4+9+11=24，如果第二步是先合并2，3堆，則代價為7，得到4  7，最后一次合并代價為11，總代價為4+7+11=22；問題是：找出一種合理的方法，使總的代價最小。輸出最小代價。

第一行一個數(shù)N表示沙子的堆數(shù)N。 第二行N個數(shù)，表示每堆沙子的質量。  < =1000

合并的最小代價

零基礎同學可以先學習視頻課程，包含C/C++、Python、百練、藍橋杯輔導、算法數(shù)據(jù)結構等課程，提供視頻講解以及配套習題，還有老師答疑，點擊這里了解課程詳情

名校訓練 動態(tài)規(guī)劃