网站隐私声明模板,项目分享网,想做一个个人网站怎么做,小程序一年费用多少钱N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆#xff0c;并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。 例如#xff1a; 1 2 3 4#xff0c;有不少合并方法1 2 3 4 3 3 4(3) 6 4… N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。 例如 1 2 3 4有不少合并方法 1 2 3 4 3 3 4(3) 6 4(9) 10(19) 1 2 3 4 1 5 4(5) 1 9(14) 10(24) 1 2 3 4 1 2 7(7) 3 7(10) 10(20) 括号里面为总代价可以看出第一种方法的代价最低现在给出n堆石子的数量计算最小合并代价。 Input第1行N2 N 100) 第2 - N 1N堆石子的数量1 Aii 10000)Output输出最小合并代价Sample Input 4
1
2
3
4 Sample Output 19 http://www.cnblogs.com/qq-star/p/4161143.html大佬的详细解答 1 #includeiostream2 #includealgorithm3 #includecstdio4 #includecstring5 using namespace std;6 7 const int INF100000000;8 9 int N;
10 int dp[105][105],sum[105][105],a[105];
11
12 int main()
13 { scanf(%d,N);
14 for(int i1;iN;i) scanf(%d,a[i]);
15 for(int i1;iN;i){
16 dp[i][i]0;
17 sum[i][i]a[i];
18 }
19 for(int len1;lenN;len){
20 for(int i1;iNilenN;i){
21 int jleni;
22 dp[i][j]INF;
23 for(int ki;kj;k){
24 sum[i][j]sum[i][k]sum[k1][j];
25 int temdp[i][k]dp[k1][j]sum[i][j];
26 if(dp[i][j]tem) dp[i][j]tem;
27 }
28 }
29 }
30 printf(%d\n,dp[1][N]);
31 } 转载于:https://www.cnblogs.com/zgglj-com/p/6914831.html
