设有N堆石子排成一排其编号为123…N。每堆石子有一定的质量可以用一个整数来描述现在要将这N堆石子合并成为一堆。每次只能合并相邻的两堆合并的代价为这两堆石子的质量之和合并后与这两堆石子相邻的石子将和新堆相邻合并时由于选择的顺序不同合并的总代价也不相同。例如有4堆石子分别为 1 3 5 2 我们可以先合并1、2堆代价为4得到4 5 2 又合并 12堆代价为9得到9 2 再合并得到11总代价为491124如果第二步是先合并23堆则代价为7得到4 7最后一次合并代价为11总代价为471122。问题是找出一种合理的方法使总的代价最小输出最小代价。输入格式第一行一个数N表示石子的堆数N。第二行N个数表示每堆石子的质量(均不超过1000)。输出格式输出一个整数表示最小代价。数据范围1≤N≤3001≤N≤300输入样例4 1 3 5 2输出样例22思路区间DP。On³也能过。代码#includebits/stdc.h using namespace std; int a[10003],n,ans0,dp[303][303]; int main(){ memset(dp,0x3f,sizeof(dp)); cinn; for(int i1;in;i) cina[i],a[i]a[i-1],dp[i][i]0; for(int len2;lenn;len){ for(int l1;ln-len1;l){ int rllen-1; for(int ml;mr;m){ dp[l][r]min(dp[l][r],dp[l][m]dp[m1][r]a[r]-a[l-1]); } } } coutdp[1][n]; return 0; }