运用区间dp的思想来思考
状态表示：所有合并第i堆到第j堆果子的集合
属性：min
状态计算/子集划分：上一次合并了哪两堆果子，即上一次的中断点是哪
中断点在i+1 合并[i]和[i+1,j] dp[i][j]=dp[i][i]+dp[i+1][j]+sum[i,j]中断点在i+2 合并[i,i+1]和[i+2,j] dp[i][j]=dp[i][i+1]+dp[i+2][j]+sum[i,j]...中断点在j-1 合并在[i,j-1]和[j] dp[i][j]=dp[i][j-1]+dp[j][j]+sum[i,j]
初始化：全为无穷大
边界：dp[i][i]=0
#include #include #include using namespace std;const int N=305;int a[N];int s[N];int dp[N][N];int main(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i]; memset(dp,0x3f,sizeof dp); for(int i=1;i<=n;i++) dp[i][i]=0; for(int len=2;len<=n;len++) for(int i=1;i+len-1<=n;i++) { int j=i+len-1; for(int k=i;k