P1775 题解

· · 题解

题目传送门

思路

本题考察基本的区间 DP。

令 f_{l,r} 表示区间 [l,r] 合并成一堆的最小代价。

初始化不难想。既然要求最小值，就可以将 f 全部赋值为 \infty。在还未合并前，一共有 N 堆石子，它们的代价为 0，所以初始化 f_{i,i}=0。

然后考虑转移。一个大区间 [l,r] 可以由两个小区间 [l,k] 和 [k+1,r] 合并得到。合并 [l,r] 内的两堆石子所需代价是 \sum_{i=l}^rm_i，可以推出转移方程式为：

f_{l,r}\gets\min(f_{l,r},f_{l,k}+f_{k+1,r}+\sum_{i=l}^rm_i)

最终答案即为 f_{1,N}。

那么枚举顺序是什么？区间 DP 的转移是由小区间合并成为大区间，所以要先枚举区间长度 len。然后就要枚举左端点 l，由于确定了区间长度，就可以得到区间右端点 r=l+len-1。最后再枚举中间点 k。

由于 \sum_{i=l}^rm_i 可以通过前缀和预处理得到，故最终时间复杂度为 \mathcal{O}(N^3)。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=300+10,MAX=1e8;
int a[N],p[N],dp[N][N];
int main(){
    int n=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        p[i]=p[i-1]+a[i];
    }
#define sum(l,r) p[r]-p[l-1]
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
            dp[i][j]=MAX;
    for(int len=2;len<=n;++len)
        for(int l=1;l+len-1<=n;++l){
            int r=l+len-1;
            for(int k=l;k<r;++k)
                dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum(l,r));
        }
    printf("%d\n",dp[1][n]);
    return 0;
}