【算法|动态规划 | 区间dp No.2】AcWing 1068.环形石子合并

Myth丶恋晨 2024-04-27 07:02 72阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]  
> 欢迎 点赞? 收藏✨ 留言✉ 加关注?本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[AcWing算法提高学习专栏][AcWing]】【[手撕算法系列专栏][Link 2]】  
> ?本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助  
> ?**希望我们一起努力、成长，共同进步**。

**原题链接：[点击直接跳转到该题目][Link 3]**

#### 目录 ####

*  1️⃣题目描述
 *  2️⃣题目解析
 *  3️⃣解题代码

## 1️⃣题目描述 ##

![在这里插入图片描述][23384f7e76b14ddda58ab05dfa9196af.png]  
![在这里插入图片描述][7c9d1a8810c84d0e9309535c577ca51f.png]

## 2️⃣题目解析 ##

本题跟普通的链式石子合并不同的点就是由链式改为了环式数组了，那我们可以想一个方法将这个环式数组变为链式数组。

由于本题是一个链式数组，所以最终的答案不一定是`[1,n]`区间，也可能是`[2,n + 1]`，`[3,n + 2]`…`[n,n + (n - 1)]`。

> 例如：环形（a,b,c,d）最终的结果区间可能是\[a,b,c,d\]、\[b,c,d,a\]、\[c,d,a,b\]、\[d,a,b,c\]4种区间中的任意一种。

所以我们本题的解题策略是**将环形数组转换为链式数组（即将其复制一遍连接在原数组的后面）**。即`(a,b,c,d,a,b,c,d)`。这样的话我们就可以使用链式数组的解决方法来解决本题了。

## 3️⃣解题代码 ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    
    const int N = 410,INF = 0x3f3f3f3f;
    int f[N][N],g[N][N];
    int arr[N],s[N];
    
    int main()
    {
        
        int n;
        cin >> n;
        for(int i = 1;i <= n;i++)
        {
        
            cin >> arr[i];
            arr[i + n] = arr[i];
        }
        for(int i = 1;i <= 2 * n;i++) s[i] = s[i - 1] + arr[i]; // 创建前缀和数组
        
        memset(f,0x3f,sizeof f);
        memset(g,-0x3f,sizeof g);
        
        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;
                else
                {
        
                     for(int k = i;k < j;k++)
                    {
        
                        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]);
                    }
                }
               
            }
        }
        
        int max_Res = -INF,min_Res = INF;
        for(int i = 1;i <= n;i++)
        {
        
            min_Res = min(min_Res,f[i][i + n - 1]);
            max_Res = max(max_Res,g[i][i + n - 1]);
        }
        cout << min_Res << endl << max_Res << endl;
        return 0;
    }

**最后代码就顺利通过啦！！！**

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[AcWing]: https://blog.csdn.net/m0_74352571/category_12481646.html
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[Link 3]: https://www.acwing.com/problem/content/1070/
[23384f7e76b14ddda58ab05dfa9196af.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/8aa9236a1a984184ac37bd9a79231731.png
[7c9d1a8810c84d0e9309535c577ca51f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/5335dfecbd654ae9b62ed09d567b24cd.png