J

J - Pangu and Stones 区间dp

题目大意：

给你n堆石头，对这n堆石头进行合并，要求每次合并的石头堆数不能小于 (l)，也不能大于 (r) ，每次合并的代价是合并的石头的数量，问将所有的石头合并的最小代价是多少，如果无法合并成一堆则输出0。

题解：

这个和石头合并很像，但是多了一维石头的堆数，所以可以定义 (dp[i][j][k]) 表示从 (i) 到 (j) 有 (k) 堆石头的最小代价。最后答案输出 (dp[1][n][1]) 即可。

但是中间要保证每次合并数量 (x) 是在区间 ([l,r]) ，合并有两种方式：

• 第一种就是合并成一堆，这个则需要花费代价
• 第二种就是 (k) 堆由 1 和 (k-1) 组合在一起，这个不需要花费代价。为什么是 1 和 (k-1)，而不是 (x) 和 (k-x) 这个应该显而易见，因为我只需要找到第一堆的最优位置即可，遍历这个 (x) 最后得到的结果其实和找到第一堆的最优位置是一样的。

转移方程：

当 (k==1) (dp[i][j][k]=min(dp[i][j][k],dp[i][x][1]+dp[x+1][j][y]+sum[j]-sum[i-1]))

其他 (dp[i][j][k]=min(dp[i][j][k],dp[i][x][1]+dp[x+1][j][k-1]))

但是注意当 (k==1) 的时候，这个转移必须合法转移，也就是合并的堆数一定要在区间 ([l,r])，所以需要一个数组来求 $dp[x+1][j][y] $ y必须满足条件 ： (l-1=<y<=r-1) ，

所以就重新开一个数组 (pre[i][j]) 表示区间([l,r]) 合并的堆数是 ([l-1,r-1]) 的最小代价。

所以最后的转移方程就是：

if(k==1) dp[i][j][k]=min(dp[i][j][k],dp[i][x][1]+pre[x+1][j]+sum[j]-sum[i-1]);
else dp[i][j][k]=min(dp[i][j][k],dp[i][x][1]+dp[x+1][j][k-1]);
           

代码：

#include <bits/stdc++.h>
#define id first
#define val second
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn=110;
typedef long long ll;
ll dp[maxn][maxn][maxn],a[maxn],sum[maxn],pre[maxn][maxn];

int main(){
    int n,l,r;
    while(~scanf("%d%d%d",&n,&l,&r)){
        sum[0]=0;
        memset(dp,inf64,sizeof(dp));
        memset(pre,inf64,sizeof(pre));
        dp[0][0][0]=0;
        for(int i=1;i<=n;i++) {
            scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i],dp[i][i][1]=0;
            if(1>=l-1&&1<=r-1) pre[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=1;k<=r;k++){
                    for(int x=i;x<=j;x++){
                        if(k==1) dp[i][j][k]=min(dp[i][j][k],dp[i][x][1]+pre[x+1][j]+sum[j]-sum[i-1]);
                        else dp[i][j][k]=min(dp[i][j][k],dp[i][x][1]+dp[x+1][j][k-1]);
                        if(k>=l-1&&k<=r-1) pre[i][j]=min(pre[i][j],dp[i][j][k]);
//                        printf("dp[%d][%d][%d]=%lld pre[%d][%d]=%lld
",i,j,k,dp[i][j][k],i,j,pre[i][j]);
                    }
                }
            }
        }
        ll ans=dp[1][n][1];
        if(ans<inf64) printf("%lld
",ans);
        else printf("0
");
    }
    return 0;
}