本题的限制是只能合并相邻区间,要是没有这个限制就成贪心问题了
题目分析
先把大哥招牌搬上来压下场子(其实懒得写了)
做些解释
- 状态
f[i][j]
的计算中,化整为零,通常都是按照最后一步来划分,即把最后一次合并分为,左边[i,k]
一大坨和右边[k+1,j]
一大坨做合并(k取i到j-1,因为两边至少都要有一堆),并且只能相邻两堆合并,所以最后左边和右边是完全独立的变成两大坨的,要求最终的一大坨的min,只需分别求之前的这两坨的最小,然后和最后合并的代价(也就是石子总质量)一块加起来就行,而总质量就是i到j所有质量之和,可以用前缀和求。综上我们有f[i][j] = min(f[i][k],f[k+1][j]) + s[j] - s[i-1]
算法复杂度
先枚举长度,再枚举左端点(知道长度知道左端点等于知道了右端点),再枚举左端点到右端点如何分成两大坨[i,k]和[k+1,j],复杂度O(n^3),n=300,$300^3$==2.7e7 一秒内出解,很香
C++ 代码
绝大部分区间DP问题都是——先枚举区间长度,再枚举区间左端点
区间长度为1表示就一堆石子,没兴趣搬它,消耗为0(f全局变量本身就是0),故区间长度从2开始即可
#include <iostream>
using namespace std;
const int N = 310;
int n;
int s[N]; //前缀和
int f[N][N]; //状态表示
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>s[i], s[i]+=s[i-1]; //直接求前缀和
for(int len=2;len<=n;len++) //枚举区间长度
for(int i=1;i+len-1<=n;i++) //枚举左端点,判断右端点不要出界
{
int j = i+len-1; //右端点j
f[i][j] = 1e8; //求最小值前先置为无穷大
for(int k=i;k<=j-1;k++)
f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + s[j] - s[i-1]);
}
cout<<f[1][n]<<endl;
return 0;
}