@[_Mikasa](/user/400245) 想想你循环 $k$ 的定义是啥
by bamboo1030 @ 2023-05-03 21:21:43
@[bamboo123](/user/369181) 断点啊
by _Mikasa @ 2023-05-03 21:23:26
@[bamboo123](/user/369181) 因为我做模板的时候就是 k+1 而且我觉得也应该是k+1
by _Mikasa @ 2023-05-03 21:24:26
@[_Mikasa](/user/400245) 你就是把区间 $[i,j)$ 分成 $[i,k),[k,j)$ 嘛所以得写 k 啊
by bamboo1030 @ 2023-05-03 21:25:20
@[bamboo123](/user/369181) 但是石子合并这道题就必须要k+1 要不然过不了 如果是k的话 就把k算了两次啊
by _Mikasa @ 2023-05-03 21:26:10
...
by dlsnb @ 2023-05-03 21:28:33
@[_Mikasa](/user/400245) 你发个代码我看看
by bamboo1030 @ 2023-05-03 21:29:17
你考虑它既是前一段的尾标记又是后一段的首标记
by Mikefeng @ 2023-05-03 21:30:11
@[bamboo123](/user/369181)
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,a[10000001],pre[1000001],dp[5000][5000];
int main(){
scanf("%lld",&n);
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
pre[i]=pre[i-1]+a[i];
dp[i][i]=0;
}
for(int len=1;len<=n;len++){
for(int i=1;i+len<=n;i++){
int r=i+len;
for(int k=1;k<r;k++){
dp[i][r]=min(dp[i][r],dp[i][k]+dp[k+1][r]+pre[r]-pre[i-1]);
}
}
}
printf("%lld",dp[1][n]);
return 0;
}
```
by _Mikasa @ 2023-05-03 21:32:51
@[_Mikasa](/user/400245) 说实话你这里好像狮子合并的 dp 定义是左闭右闭的所以得这么写
by bamboo1030 @ 2023-05-03 21:38:43