更多提高课题目题解,欢迎访问我的提高课学习笔记+题解总结(更新中)
分析
本题要求通过不断进行合并操作将所有能量珠最终合并至一颗,且合并当前区间时产生总能量仅受当前合并节点与各个子区间合并产生能量影响,是一道典型的区间DP问题
本题特点在于,对于任意一个能量珠,都存在两个属性,头标记值与尾标记值,且每颗珠子的尾标记与下一颗珠子的头标记一定相同
故在读取标记值时,可使用下一颗珠子的头标记值代替当前珠子的尾标记值
对于状态表示,可按照区间DP模板使用 $f_{l,r}$ 表示将从能量珠 $l$ 到能量珠 $r-1$ 的区间合并所能产生的最大能量值,由于最后一个珠子需要用到其后一颗珠子的头标记值,所以 $f_{l,r}$ 代表实际区间为 $[l,r)$ ,避免数组越界
由于珠子在项链上呈环状放置,故需按照处理环形问题方式对数据进行处理,即将序列延长至两倍,使 $w_{i+n}$ 的值等于 $w_i$ ,然后进行区间DP
由于对于同一颗能量珠 $k$ ,其头标记既会在以 $k-1$ 为结尾的区间中被使用,又会在以 $k$ 为开头的区间中使用,所以当以 $k$ 为子区间划分中间节点时,其会分别在左右区间中出现,状态转移方程为
$$
f_{l,r}=max(f_{l,k}+f_{k,r}+calc_{l,k,r}) (l < k < r)
$$
其中 $calc$ 代表当前一步合并所产生的能量值,由于每个状态代表的区间实际为左闭右开,所以需要将区间按从小到大至 $n+1$ 进行区间DP,而不是常见模板中的长度 $n$
此方法需枚举区间大小 $len$ ,区间左端点 $l$ 与区间中间节点 $k$ ,共三层循环,时间复杂度为 $O(n^3)$
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=210;//环形问题故空间限度为题目数据范围两倍
int n,w[N],f[N][N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
w[i+n]=w[i];//环形问题预处理
}
for(int len=3;len<=n+1;len++)//枚举区间大小,注意范围为从3至n+1
{
for(int l=1;l+len-1<=2*n;l++)//枚举左端点
{
int r=l+len-1;//计算右端点
for(int k=l+1;k<r;k++)//枚举中间节点
f[l][r]=max(f[l][r],f[l][k]+f[k][r]+w[l]*w[k]*w[r]);//按题目要求进行合并产生能量计算
}
}
int ans=0;
for(int i=1;i<=n;i++)//比较,获得最终答案
ans=max(ans,f[i][i+n]);//注意区间范围为从i至i+n而非从i至i+n-1
printf("%d",ans);
return 0;
}
先来关注一波~