@[hhhcj](/user/1021663) 可以这样吧
by lucy2012 @ 2024-04-27 09:52:33
@[lucy2012](/user/1252442) 您的小 bug 有点多。
by HSS_Indigo @ 2024-04-27 09:52:47
`int l=i,r=j+i-1;` 应该是 `l=j`
by littlebug @ 2024-04-27 09:52:52
@[lucy2012](/user/1252442)
对于输入样例中的石子堆质量 [2, 5, 3, 1],最优的合并方式是:
1.合并第 1 堆和第 2 堆,代价为 2 + 5 = 7
2.合并第 3 堆和第 4 堆,代价为 3 + 1 = 4
3.合并合并后的两堆石子,代价为 7 + 4 = 11
4.总共的最小代价为 7 + 4 + 11 = 22
by yjz468 @ 2024-04-27 09:52:53
@[hhhcj](/user/1021663) 没错啊 区间dp 楼主写挂了吧
by _8008008 @ 2024-04-27 09:53:17
$i$ 初值为 2,显然不会赋值到 $dp[1][n]$。
将 $i$ 赋值为 1 即可。
还有,应提前将 dp 赋值为 inf,你这么写,很有可能会有一些只在调用时 没有赋值。
还有,$l$ 应等于 $j$,因为 $i$ 是长度,$j$ 才是左端点。
代码如下:
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,a[310],dp[310][310],sum[310];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j) dp[i][j]=0x7ffffff;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j+i-1<=n;j++){
int l=j,r=j+i-1;
for(int k=l;k<r;k++)
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
}
}
cout<<dp[1][n];
return 0;
}
```
by Liyhzh_C202712 @ 2024-04-27 09:53:25
@[HSS_Indigo](/user/347214) 共有三个。
by Liyhzh_C202712 @ 2024-04-27 09:55:19
@[lucy2012](/user/1252442) 改完了,已AC:
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,a[310],dp[310][310],sum[310];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int len=2;len<=n;len++){
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
dp[l][r]=0x7fffffff;
for(int k=l;k<r;k++)
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
}
}
cout<<dp[1][n];
return 0;
}
```
by yjz468 @ 2024-04-27 09:55:25
@[littlebug](/user/541634) @[yjz468](/user/937773) @[Liyhzh_C202712](/user/1068500) 谢谢啦!以ac
by lucy2012 @ 2024-04-27 10:01:44
就是$l=j$的问题啦
by lucy2012 @ 2024-04-27 10:03:22