动态规划—区间DP(一)

简介: AcWing算法提高课内容,本文讲解 动态规划

前言

AcWing算法提高课内容,本文讲解 动态规划

本篇包括以下题目:

⭐️ AcWing 1068. 环形石子合并

⭐️ AcWing 320. 能量项链

⭐️ AcWing 479. 加分二叉树

⭐️ AcWing 1069. 凸多边形的划分


写博客有哪里不完善的地方或者有哪里表达错误希望大家提出来,博主会立即改正!望大家海涵


本文需要先自修基础:区间DP


环形石子合并

题目要求

题目描述:

image.png

输入格式:

第一行包含整数 n ,表示共有 n  堆石子。

第二行包含 n 个整数,分别表示每堆石子的数量。

输出格式:

输出共两行:

第一行为合并得分总和最小值,

第二行为合并得分总和最大值。

数据范围:

1n200

输入样例:

4
4 5 9 4

输出样例:

43
54

思路分析

环形的问题我们都可以变环为线,即我们开两倍的大小,然后以n为长度进行枚举即可,下面给一个示例图:

image.png

这样,我们直接对展开的直线以长度为 6 进行遍历,和直接枚举一个环的效果是一致的,为了更快的求出一段区间的和,可以使用前缀和的思维进行优化,前缀和讲解见博客:前缀和算法

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 410;
int f[N][N], g[N][N];
int w[N], s[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> w[i], w[i + n] = w[i];
    for (int i = 1; i <= 2 * n; i ++ ) s[i] = s[i - 1] + w[i];
    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= 2 * n; i ++ ) g[i][i] = 0;
    for (int len = 2; len <= n; len ++ )
        for (int l = 1; l + len - 1 <= 2 * n; l ++ )
        {
            int r = l + len - 1;
            for (int k = l; k < r; k ++ )
            {
                f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                g[l][r] = min(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);   
            }
        }
    int maxv = 0, minv = 0x3f3f3f3f;    
    for (int i = 1; i <= n; i ++ )
    {
        maxv = max(maxv, f[i][i + n - 1]);
        minv = min(minv, g[i][i + n - 1]);
    }
    cout << minv << endl << maxv;
    return 0;
}

能量项链

题目要求

题目描述:

image.png

输入格式:

image.png

输出格式:

输出只有一行,是一个正整数E,为一个最优聚合顺序所释放的总能量。

数据范围:

image.png

输入样例:

4
2 3 5 10

输出样例:

710

思路分析

环形石子合并 的一个升级,思路还是一致的,对应到代码上有一些微处理,比如合并的长度最少是3,区间dp间断点的枚举必须从 l + 1  进行枚举

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
int f[N][N];
int w[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> w[i], w[i + n] = w[i];
    for (int len = 3; len <= n + 1; len ++ )
        for (int l = 1; l + len - 1 <= 2 * n; l ++ )
        {
            int r = l + len - 1;
            for (int k = l + 1; k < r; k ++ )
                f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
        }
    int maxv = 0;
    for (int i = 1; i <= n; i ++ ) maxv = max(maxv, f[i][i + n]);
    cout << maxv << endl;
    return 0;
}




目录
相关文章
|
算法
【学会动态规划】最小路径和(9)
【学会动态规划】最小路径和(9)
59 0
|
10月前
|
算法
动态规划—(背包问题)
动态规划—(背包问题)
|
存储 算法
动态规划之背包问题
动态规划之背包问题
109 0
|
人工智能 BI
动态规划(DP)——背包问题
动态规划(DP)——背包问题
动态规划:完全背包问题
动态规划:完全背包问题
85 0
动态规划-完全背包
前言 我们上篇文章学习了动态规划01背包的问题,本篇文章我们继续学习完全背包。大家可以在学习完01背包的基础上再进行学习,比较其两者的解题差异。
动态规划-公共子序列问题
前言 前面我们学习了动态规划的背包类型问题,其中涉及01背包,完全背包,多重背包。现在我们来继续学习动态规划的公共子序列问题。
爬楼梯(动态规划)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
78 0