---
title: "能量项链"
created: 2025-11-28
tags:
  - 算法
---

# 能量项链

## 题目 [能量项链](https://www.acwing.com/problem/content/322/)

![[image-d051c2c3.png]]

## 思路分析

在上一道题环形的基础上 再加了一个东西

现在不是i-j里分成两半两两合并 而是i,k--k,j合并成ij

多了一个k限制

![[image-faa76454.png]]

在 环形石子 中，每个石头只有单一的参数，而本题有两个参数，也就意味着我们需要在细节上做出改变

经过观察我们发现，合并两个石头 (a,b),(b,c)的操作就像是矩阵乘法一样，合并完后就变成了 (a,c) 因此我们可以离散的来存储每个参数，具体如下所示：

![[image-23700857.png]]

这样 状态表示 就更新为：当前合并的石子堆的左端石头的左参数是 l，右端石头的右参数是 r的方案

这样对应的 初始状态 本来应该是一个有着 二元属性 的石头，现在就变成了长度为 2的区间

这样合并区间后，需要记录的新石头的参数也刚好是 区间的两端 对应的参数，如下图所示：

![[image-66b87aa4.png]]

而且这里我们的转移方程也要修改为 $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}$:

![[image-6c928ab7.png]]

初始状态： $f\_{l,l+1}=0 (1≤l≤n)$*目标状态：*
$ f\_{1,n+1}$

## 代码实现

```cpp
 #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;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[石子合并|石子合并]] 🏠 [[00-刷题理模型]] ➡️ [[打家劫舍|打家劫舍]]