---
title: "环形石子合并"
created: 2025-11-28
tags:
  - 算法
---

# 环形石子合并

## 题目 [环形石子合并](https://www.acwing.com/solution/content/59932/)

![[image-e72f3a94.png]]

## 思路分析

在之前那题的基础上加上了个环形 以及最大花费

环形相邻 情况已经碰到很多次了

把链延长两倍，变成 2n，其中 i和 i+n是相同的两个堆，然后直接套 区间DP 模板

状态表示—集合$f\_{en,l,r}$：*当前合并的石子堆的大小为 len，且石子堆的左端点是 l，右端点是 r的方案*

*状态表示—属性*$f\_{len,l,r}$：方案的费用最大/最小（本题两者都要求）

状态计算—$f\_{len,l,r}$:

![[image-e40a81d6.png]]

初始状态： $f\_{1,i,i}(1≤i≤n)$

目标状态：$f\_{n,1,n}$

len这一维的空间可以省去因为 r−l+1=len，也就保证了在已知 l和 r的情况下，不会出现状态定义重复的情况

这俩题都是基于 相邻两堆石子俩俩合并的 所以用区间dp 如果是任意两堆或者多堆合并 就用贪心

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=210,M=N*2,INF=0x3f3f3f3f;

int a[M],s[M];

int f[M][M],g[M][M];

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++){

        cin>>a[i];

        a[i+n]=a[i];

    }

    for(int i=1;i<=n*2;i++)

        s[i]=s[i-1]+a[i];

    memset(f,0x3f,sizeof f);//求最小 初始化inf

    memset(g,-0x3f,sizeof g);//求最大 初始化-inf

    for(int len=1;len<=n;len++){ // 枚举区间长度

        for(int i=1;i+len-1<=n*2;i++){// 枚举起点

            int j=i+len-1;//计算终点

            if(len==1){//最小区间特判

                f[i][j]=g[i][j]=0;

                continue;

            }

            for(int k=i;k<=j-1;k++){// 枚举分割点，构造状态转移方程

                //k只能在一边 类似于二分的划法 一般把k放左边 k+1为右区间起点

                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);

                g[i][j]=max(g[i][j],g[i][k]+g[k+1][j]+s[j]-s[i-1]);

            }

        }

    }

    //目标状态中找出方案 因为是环形 所以不能直接1-n 而是在所以1-n长度中找max/min

    int minv = INF, maxv = -INF;

    for (int l = 1; l <= n; ++ l){

        minv = min(minv, f[l][l + n - 1]);

        maxv = max(maxv, g[l][l + n - 1]);

    }

    printf("%d\n%d\n", minv, maxv);

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[棋盘分割|棋盘分割]] 🏠 [[00-刷题理模型]] ➡️ [[石子合并|石子合并]]