P1775题解

Hollis_Yang · 2021-12-20 17:50:33 · 题解

这么简单的题居然没人来做？

这是一道区间 dp 的模板题，比较适合初学区间 dp 的同学做。

废话不多说，开始讲吧。

我们设dp[i][j]为m[i]到m[j]合并的最小代价。

定义了状态以后，我们来想 dp 转移方程。

区间 dp 的核心思想就是把两个区间的答案合并。

所以我们每次在i到j中枚举一个断点k。

假设我们已经把i到k和k+1到j已经合并好了。

那么i到j合并的代价就是i到k合并的最小代价加上k+1到j合并的最小代价再加上把这两个区间合并的代价。

把这两区间合并的代价就是i到j的石子质量的和。

我们设d(i,j)表示i到j的石子质量的和。

可以得到 dp 转移方程：dp[i][j]=min(dp[i][k]+dp[k+1][j]+d(i,j))。

如何快速查询表示i到j的石子质量的和呢？

我们可以使用前缀和 O(1) 查询。

这样我们就得到了一个时间复杂度 O(n^3) 的算法。

最后，根据dp[i][j]的定义，dp[1][n]即为答案。

AC 代码

#include<bits/stdc++.h>
#define ll long long
#define un unsigned
#define pb push_back
#define mp makepair
using namespace std;
template<typename T> inline void read(T &x){
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
template<typename T> inline void write(T x){
    short st[30],tp=0;
    if(x<0) putchar('-'),x=-x;
    do st[++tp]=x%10,x/=10; while(x);
    while(tp) putchar('0'|st[tp--]);
}
#define wr write
#define rd read
#define pk putchar(' ')
#define ed puts("")
int dp[301][301],i,j,k,l,m[501],n,d[501];
signed main(){
    rd(n);
    for(i=1;i<=n;i++) rd(m[i]);
    for(i=1;i<=n;i++) d[i]=d[i-1]+m[i];//前缀和
    for(l=1;l<n;l++){
        for(i=1,j=l+1;j<=n;j++,i++){
            dp[i][j]=0x7ffffff;//自己思考一下为什么必须在循环里设初值
            for(k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+d[j]-d[i-1]);//dp转移方程
        }
    }
    wr(dp[1][n]);
}

蒟蒻的第二篇题解 qwq。