鏈接：https://vjudge.net/problem/HihoCoder-1636
思路：區(qū)間dp，可以說是石子合并的加強版，只是因為由相鄰合并改為了一個范圍合并，所以我們要在原來dp上多加一維，dp[l][r][k]表示從l到r區(qū)間被分成k堆所需要的最小值，k=1時表示整個區(qū)間合并完成，狀態(tài)表示如下：
k>2 dp[l][r][k] = min(dp[l][r][k],dp[l][d][1]+dp[d+1][r][k-1])
k=1 dp[l][r][1] = min(dp[l][r][1],dp[l][r][k]+sum(r)-sum(l-1))
巧妙的地方就是把答案放到k=1的地方去，這樣我們只用在合并的時候加上前綴和，也算是一個套路吧，分解區(qū)間的時候不加前綴和，因為之前的都已經(jīng)算好了，合并的時候更新當(dāng)前狀態(tài)的最優(yōu)解，加上前綴和。
代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,L,R;
const int maxn = 500;
const ll INF = 1e18;
ll dp[maxn][maxn][maxn];
ll sum[maxn];
int a[maxn];

int main(){
    while(~scanf("%d%d%d",&n,&L,&R)){
        sum[0] = 0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            sum[i] = sum[i-1] + a[i];
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                for(int k=1;k<=n;k++){
                    dp[i][j][k] = INF;
                }
            }
        }
        for(int i=0;i<=n;i++)dp[i][i][1] = 0;
        for(int len=2;len<=n;len++){
            for(int l=1;l+len-1<=n;l++){
                int r = l+len-1;
                for(int p=2;p<=len;p++){//枚舉大于1的情況
                    for(int k=l;k<r;k++){//拆分區(qū)間
                            dp[l][r][p] = min(dp[l][r][p],dp[l][k][1]+dp[k+1][r][p-1]);
                    }
                }
              //將最優(yōu)解合并到k=1的時候，更新當(dāng)前狀態(tài)的最優(yōu)解
                for(int k=0;k<=n;k++){
                    if((k>=L&&k<=R)||(k==0&&len>=L&&len<=R))
                    dp[l][r][1] = min(dp[l][r][1],dp[l][r][k]+sum[r]-sum[l-1]);
                }
            }
        }
        printf("%lld\n",dp[1][n][1]>=INF?0:dp[1][n][1]);
    }
    return 0;
}