能量项链
题目 能量项链
思路分析
在上一道题环形的基础上 再加了一个东西
现在不是i-j里分成两半两两合并 而是i,k--k,j合并成ij
多了一个k限制
在 环形石子 中，每个石头只有单一的参数，而本题有两个参数，也就意味着我们需要在细节上做出改变
经过观察我们发现，合并两个石头 (a,b),(b,c)的操作就像是矩阵乘法一样，合并完后就变成了 (a,c) 因此我们可以离散的来存储每个参数，具体如下所示：
这样 状态表示 就更新为：当前合并的石子堆的左端石头的左参数是 l，右端石头的右参数是 r的方案
这样对应的 初始状态 本来应该是一个有着 二元属性 的石头，现在就变成了长度为 2的区间
这样合并区间后，需要记录的新石头的参数也刚好是 区间的两端 对应的参数，如下图所示：
而且这里我们的转移方程也要修改为 \(f_{l,r}=max(f_{l,k}+f_{k,r}+E_{l,r})\)
以往的 区间DP 我们是把区间 [a,b]拆分为 [a,k]和[k+1,b]因为 同一个石子 只会被合并到 一个石子堆 里
但本题合并魔法石时，分割点 k要被分到 左侧石子堆的右端点 和 右侧石子堆的左端点 中
因此，参数 k要作为两个区间的共同端点来使用，即 [a,k]和 [k,b] 此外我们原来只需要合并 n个石头，这样转换后就要合并 n+1个石头了
状态表示—集合\(f_{l,r}\):当前合并的石子堆的左端石头的左参数是 l，右端石头的右参数是 r的方案 状态表示—属性 \(f{l,r}\):方案的费用最大 状态计算—\(f_{l,r}\):
初始状态： \(f_{l,l+1}=0 (1≤l≤n)\)目标状态： $ f_{1,n+1}$
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=110,M=2*N;
int w[M];
int f[M][M];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>w[i],w[n+i]=w[i];
memset(f,-0x3f,sizeof f);//求最大 初始化-inf
for(int len=2;len<=n+1;len++){//区间长度 此时为共用k (i,k k,j) k做两个用 单一区间长度最小为2
for(int i=1;i+len-1<=n*2;i++){//枚举起点
int j=i+len-1;//算出终点
if(len==2){//最小区间特判
f[i][j]=0;
continue;
}
for(int k=i+1;k<j;k++){//枚举分割点 如上分析此时k共用
f[i][j]=max(f[i][j],f[i][k]+f[k][j]+w[i]*w[k]*w[j]);
}
}
}
int res=0;
for(int i=1;i<=n;i++)
res=max(res,f[i][i+n]);
cout<<res;
return 0;
}
💬 评论