LOJ P10147 石子合并题解

向右看齐 2021-10-19 19:16 253阅读 0赞

### Analysis ###

区间dp+前缀和

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define maxn 210
    #define INF 2139062143
    using namespace std;
    int n,minn=INF,maxx;
    int a[2*maxn],dp_min[2*maxn][2*maxn],dp_max[2*maxn][2*maxn],sum[2*maxn];
    int main()
    {
        memset(dp_min,127,sizeof(dp_min));
        scanf("%d",&n);
        for(int i=1;i<=n;i++) 
        {
            scanf("%d",&a[i]);
            a[i+n]=a[i];
        }
        sum[1]=a[1];
        for(int i=2;i<=2*n;i++) sum[i]=sum[i-1]+a[i];
        for(int i=1;i<=2*n;i++)
        {
            dp_min[i][i]=0;
            dp_max[i][i]=0;
        } 
        for(int len=2;len<=n;len++)
        {
            for(int i=1;i<=2*n;i++)
            {
                int j=i+len-1;
                if(j>2*n) break;
                for(int k=i;k<j;k++)
                {
                    dp_min[i][j]=min(dp_min[i][j],dp_min[i][k]+dp_min[k+1][j]+sum[j]-sum[i-1]);
                    dp_max[i][j]=max(dp_max[i][j],dp_max[i][k]+dp_max[k+1][j]+sum[j]-sum[i-1]);
                    
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            minn=min(minn,dp_min[i][i+n-1]);
            maxx=max(maxx,dp_max[i][i+n-1]);
        }
        printf("%d\n%d",minn,maxx);
        return 0;
    } 
    /*
    4
    4 5 9 4
    */

请各位大佬斧正（反正我不认识斧正是什么意思）

转载于:https://www.cnblogs.com/handsome-zyc/p/11309196.html

发表评论取消回复

表情：

评论列表（有 0 条评论，253人围观）

还没有评论，来说两句吧...

相关阅读

相关区间DP | 2：环上的合并石子 —— 例题：合并石子（环形）

本文是在[区间DP | 1：矩阵链乘问题（含优化） —— 例题：矩阵链乘、合并石子][DP _ 1_ _] 上的升级（建议先看链接文章）。从链到环的改变，但本质还是区间dp问题

傷城~/ 2023年07月17日 07:28/ 0 赞/ 1 阅读

相关 P1880-[NOI1995]石子合并

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

蔚落/ 2023年06月01日 08:51/ 0 赞/ 7 阅读

相关石子合并问题（区间dp）

include <iostream> using namespace std; define ios ios_base::sync_with_stdio

分手后的思念是犯贱/ 2022年10月11日 00:59/ 0 赞/ 170 阅读

相关 282 石子合并（区间dp）

1. 问题描述：设有 N 堆石子排成一排，其编号为 1，2，3，…，N。每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。每次只能合并相邻的两

朱雀/ 2022年09月12日 12:49/ 0 赞/ 200 阅读

相关 dp 石子合并问题

石子合并问题：有n(N<100)堆石子，价值分别为a0,a1......a(n-1),每次将其中的相邻的两堆合并，合并的代价为两堆石子的价值和,合并后用合并之后的一堆石子代

￡神魔★判官ぃ/ 2022年08月18日 00:58/ 0 赞/ 193 阅读

相关石子合并

经典动态规划，本题的思想就是将n个石子合并的大问题逐渐从2个小石子合并的小问题逐渐推出 <pre name="code" class="cpp">inclu

野性酷女/ 2022年08月11日 08:58/ 0 赞/ 160 阅读

相关石子合并问题

在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选择相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n

傷城~/ 2022年08月02日 07:19/ 0 赞/ 194 阅读

相关【p1880】石子合并

[https://www.luogu.org/problem/show?pid=1880][https_www.luogu.org_problem_show_pid_1880]

忘是亡心i/ 2022年06月06日 01:55/ 0 赞/ 137 阅读

相关洛谷P1880 [NOI1995]石子合并

![70][] 思路：将数后面复制一份 dp【i】【j】=max（dp【i】【j】，dp【i】【k】+dp【k+1】【j】+sum【j】-sum【i-1】

叁歲伎倆/ 2022年05月26日 23:06/ 0 赞/ 173 阅读

相关 LOJ P10147 石子合并题解

Analysis 区间dp+前缀和 include<iostream> include<cstdio> include<cstring>

向右看齐/ 2021年10月19日 19:16/ 0 赞/ 254 阅读