环形石子的合并

最新推荐文章于 2024-07-20 01:59:03 发布

coder370

最新推荐文章于 2024-07-20 01:59:03 发布

阅读量207

点赞数

分类专栏：动态规划

本文链接：https://blog.csdn.net/coder370/article/details/101171310

版权

动态规划专栏收录该内容

9 篇文章

订阅专栏

这篇博客探讨了如何解决环形排列的石子合并问题。通过将环转化为链，双倍链长并从2*n-1开始枚举n的长度，最终找到合适的合并方案。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

之前的石子合并是一排的，这里是环的要将环拆成链，复制一份接在后面，因为链的长度为原来的两倍，所以应该从2*n-1枚举，每次枚举n的长度，然后从1-n找最后的答案即可。

#include <cstdio>
#include <algorithm>
using namespace std ;
const int N = 210 ;
const int INF = 0x7fffffff/2 ;
int a[N] , sum[N] ;
int f[N][N] , g[N][N] ;  
int main(){
    int n ;
    scanf ("%d",&n) ;
    for (int i = 1 ; i <= n ; i ++){
        scanf ("%d",&a[i]) ;
        a[i+n] = a[i] ;
        f[i][i] = 0 , g[i][i] = 0 ;
    }
    for (int i = 1 ; i <= 2*n ; i ++){
        sum[i] = sum[i-1] + a[i] ;
        
    }
    for (int len = 1 ; len < n ; len ++){
        for (int i = 1 ; i <= 2*n-len ; i ++){
            int j = i + len ;
            g[i][j] = INF ;
            f[i][j] = 0 ;   
            for (int k = i ; k < j ; k ++){
                g[i][j] = min(g[i][j] , g[i][k] + g[k+1][j] + sum[j] - sum[i-1])  ;
                f[i][j] = max(f[i][j] , f[i][k] + f[k+1][j] + sum[j] - sum[i-1])  ;
            }
        }    
    }
        
    int maxs = 0 , mins = INF ;
    for (int i = 1 ; i <= n ; i ++)    {
        maxs = max(maxs,f[i][i-1+n]) ;
    }
        
    for (int i = 1 ; i <= n ; i ++)    
        mins = min(mins,g[i][i-1+n]) ;
    printf ("%d\n%d\n",mins,maxs) ;
    return 0 ;
}