新手光能
请问石子合并的思路是什么？
题目描述 Description
有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。
输入描述 Input Description
有多组测试数据，输入0截止(n=0)。
每组测试数据第一行有一个整数n，表示有n堆石子。
接下来的一行有n（0< n <200）个数，分别表示这n堆石子的数目，用空格隔开
输出描述 Output Description
输出总代价的最小值，占单独的一行
样例输入 Sample Input3
1 2 3
7
13 7 8 16 21 4 18
0
样例输出 Sample Output
9
239
在线等，急！
高级光能
首先，列出石子 进行观察。A[i]为该堆中的石子个数
1.□ 2.□□ 3.□□□ 4.□□□□ 5.□□□□□
1.若石子有1堆，则无需合并，花费为0
2.若石子有2堆，则合并二者，花费为A[0]+A[1]
3.若石子有3堆，则有2种情况，①先合并A[0]、A[1]再与A[2]合并 ②先合并A[1]、A[2]再与A[0]合并
4.若石子有4堆，则有3种情况，...............
总之，在n堆中，有n-1种情况，而最后一次合并总是以某两堆合成一堆为结果。
即可将n堆划分成A[0...k] 与 A[k+1...n-1]合并，
而A[0...k] 与 A[k+1...n-1]已是最优花费，由各自向下分解所得。
（递归思想，但由于此次是二维的，即符合动态规划）
————————————————————————————————————
假设有5堆石子，则A[0...k] 与 A[k+1...n-1]的长度堆数可能为 1、4 2、3 3、2 4、1
只要其各自已为最优花费。
以上为递推向下的逻辑，在动态规划是由下而上，即5堆石子 需要长度为 2 3 4 的石子最优花费
如图。
然后开始分析算法过程，首先，最外层循环 控制石子堆长度（len=2 to n）,因为只有1堆时无需下续步骤
接着第二层循环，确定石子堆的起始堆号（i=0 to n-len）即为图中的下划线个数。
继续分析，发现还需要一层循环控制更新 A[0...k] 与 A[k+1...n-1]的花费price (k=i to j-1)
确定无遗漏后，开始编写代码过程，如下。
（注意，花费是每两两合并完的石子数依次相加，所以最后一次合并为合并堆数的总石子量）
——————————————————————————————————————————————、
由sum[i][j]表示第i堆石子到第j堆石子全部合并的总石子量。dp[i][j]为第i堆石子到第j堆合并的花费（随着动态规划的进行，会越来越越接近最优花费）dp[i][i]=0 （本身无需合并，不需花费）
即若仅两堆石子合并 则dp[i][j]=dp[i][i]+dp[j][j]+sum[i][j] = 0+0+sum[i][j]
以下用一维sum[n]进行存储，sum[i][j]=sum[j]-sum[i-1] (i!=0), sum[i][j]=sum[j] (i==0)
初级光能
f[i][j]表示从第i堆到第j堆石子合并的最小分数
f[1,n]即所求解
f[1,j]=min(f[i][k]+f[k+1][j])+第i堆石子到第j堆石子的数目之和
边界:f[i][i]=0
高级光能
f[i][j]表示从第i堆到第j堆石子合并的最小分数 f[i][j]=min(f[i][k]+f[k+1][j],f[i][j])+第i堆石子到第j堆石子的数目之和 边界：f[i][i]=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
if (i==j) f[i][j]=0;
else f[i][j]=99999999;
}
sum[0]=0;
for (int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];
}
for (int l=1;l<=n-1;l++)
{
for (int i=1;i<=n;i++)
{
int j=i+l;
if (j>n) break;
for (int k=1;k<j;k++)
{
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);
}
}
}核心代码
最优解是f[1][n]
要用到前缀和和区间动规的知识
新手光能
请解释一下外面三重循环的意思，谢谢
初级光能
for(int i=1;i<=n;i++)
{
cin>>x;
s[i]=s[i-1]+x;
}
for(int i=1;i<=n;i++)
f[i][i]=0;
for(int i=n-1;i>=1;i--)
for(int j=i+1;j<=n;j++)
for(int k=i;k<=j-1;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
cout<<f[1][n]<<endl;
资深天翼
前缀和+区间dp。
资深天翼
1
