动态规划—区间DP

举报
辰chen 发表于 2022/06/15 22:45:58 2022/06/15
【摘要】 目录 前言环形石子合并题目要求思路分析代码 能量项链题目要求思路分析代码 加分二叉树题目要求思路分析代码 凸多边形的划分题目要求思路分析代码 前言 AcWing算法提高课内...

目录

前言

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

本篇包括以下题目：

⭐️ AcWing 1068. 环形石子合并
⭐️ AcWing 320. 能量项链
⭐️ AcWing 479. 加分二叉树
⭐️ AcWing 1069. 凸多边形的划分

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

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

环形石子合并

题目要求

题目描述：

将 n n n 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。

规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 n n n 及每堆的石子数，并进行如下计算：

  • 选择一种合并石子的方案，使得做 n − 1 n−1 n−1 次合并得分总和最大。
  • 选择一种合并石子的方案，使得做 n − 1 n−1 n−1 次合并得分总和最小。

输入格式：

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

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

输出格式：

输出共两行：

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

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

数据范围：

1 ≤ n ≤ 200 1≤n≤200 1≤n≤200

输入样例：

4
4 5 9 4

  
 
    
  
  • 1
    • 
  
  • 2
    •

输出样例：

43
54

  
 
    
  
  • 1
    • 
  
  • 2
    •

思路分析

环形的问题我们都可以变环为线，即我们开两倍的大小，然后以 n n n 为长度进行枚举即可，下面给一个示例图：
在这里插入图片描述这样，我们直接对展开的直线以长度为 6 6 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;
}

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    • 
  
  • 18
    • 
  
  • 19
    • 
  
  • 20
    • 
  
  • 21
    • 
  
  • 22
    • 
  
  • 23
    • 
  
  • 24
    • 
  
  • 25
    • 
  
  • 26
    • 
  
  • 27
    • 
  
  • 28
    • 
  
  • 29
    • 
  
  • 30
    • 
  
  • 31
    • 
  
  • 32
    • 
  
  • 33
    • 
  
  • 34
    • 
  
  • 35
    • 
  
  • 36
    • 
  
  • 37
    • 
  
  • 38
    • 
  
  • 39
    • 
  
  • 40
    • 
  
  • 41
    • 
  
  • 42
    • 
  
  • 43
    •

能量项链

题目要求

题目描述：
在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链，在项链上有 N N N 颗能量珠。

能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。

并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。

因为只有这样，通过吸盘（吸盘是 Mars 人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。

如果前一颗能量珠的头标记为 m m m，尾标记为 r r r，后一颗能量珠的头标记为 r r r，尾标记为 n n n，则聚合后释放的能量为 m × r × n m \times r \times n m×r×n（Mars 单位），新产生的珠子的头标记为 m m m，尾标记为 n n n。

需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。

显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

例如：设 N = 4 N=4 N=4， 4 4 4 颗珠子的头标记与尾标记依次为 ( 2 ， 3 ) ( 3 ， 5 ) ( 5 ， 10 ) ( 10 ， 2 ) (2，3) (3，5) (5，10) (10，2) (2，3)(3，5)(5，10)(10，2)。

我们用记号 ⊕ ⊕ ⊕ 表示两颗珠子的聚合操作， ( j ⊕ k ) (j⊕k) (j⊕k) 表示第 j j j， k k k 两颗珠子聚合后所释放的能量。则第 4 、 1 4、1 4、1 两颗珠子聚合后释放的能量为： ( 4 ⊕ 1 ) = 10 × 2 × 3 = 60 (4⊕1)=10 \times 2 \times 3=60 (4⊕1)=10×2×3=60。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ( ( 4 ⊕ 1 ) ⊕ 2 ) ⊕ 3 ) = 10 × 2 × 3 + 10 × 3 × 5 + 10 × 5 × 10 = 710 ((4 \oplus 1) \oplus 2) \oplus 3) = 10 \times 2 \times 3+10 \times 3 \times 5+10 \times 5 \times 10=710 ((4⊕1)⊕2)⊕3)=10×2×3+10×3×5+10×5×10=710。

输入格式：

输入的第一行是一个正整数 N N N，表示项链上珠子的个数。

第二行是 N N N 个用空格隔开的正整数，所有的数均不超过 1000 1000 1000，第 i i i 个数为第 i i i 颗珠子的头标记，当 i < N i<N i<N 时，第 i i i 颗珠子的尾标记应该等于第 i + 1 i+1 i+1 颗珠子的头标记，第 N N N 颗珠子的尾标记应该等于第 1 1 1 颗珠子的头标记。

至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。

输出格式：

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

数据范围：

4 ≤ N ≤ 100 , 4≤N≤100, 4≤N≤100,
1 ≤ E ≤ 2.1 × 1 0 9 1≤E≤2.1×10^9 1≤E≤2.1×109

输入样例：

4
2 3 5 10

  
 
    
  
  • 1
    • 
  
  • 2
    •

输出样例：

710

  
 
    
  
  • 1
    •

思路分析

是 环形石子合并 的一个升级，思路还是一致的，对应到代码上有一些微处理，比如合并的长度最少是 3 3 3，区间dp间断点的枚举必须从 l + 1 l+1 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;
}

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    • 
  
  • 18
    • 
  
  • 19
    • 
  
  • 20
    • 
  
  • 21
    • 
  
  • 22
    • 
  
  • 23
    • 
  
  • 24
    • 
  
  • 25
    • 
  
  • 26
    • 
  
  • 27
    • 
  
  • 28
    • 
  
  • 29
    • 
  
  • 30
    • 
  
  • 31
    • 
  
  • 32
    •

加分二叉树

题目要求

题目描述：

设一个 n n n 个节点的二叉树 t r e e tree tree 的中序遍历为（ 1 , 2 , 3 , … , n 1,2,3,…,n 1,2,3,…,n），其中数字 1 , 2 , 3 , … , n 1,2,3,…,n 1,2,3,…,n 为节点编号。

每个节点都有一个分数（均为正整数），记第 i i i 个节点的分数为 d i d_i di​， t r e e tree tree 及它的每个子树都有一个加分，任一棵子树 s u b t r e e subtree subtree（也包含 t r e e tree tree 本身）的加分计算方法如下：

s u b t r e e subtree subtree 的左子树的加分 × × × s u b t r e e subtree subtree 的右子树的加分 ＋ ＋ ＋ s u b t r e e subtree subtree 的根的分数

若某个子树为空，规定其加分为 1 1 1。

叶子的加分就是叶节点本身的分数，不考虑它的空子树。

试求一棵符合中序遍历为（ 1 , 2 , 3 , … , n 1,2,3,…,n 1,2,3,…,n）且加分最高的二叉树 t r e e tree tree

输入格式：

第 1 1 1 行：一个整数 n n n，为节点个数。

第 2 2 2 行： n n n 个用空格隔开的整数，为每个节点的分数（ 0 < 0< 0< 分数 < 100 <100 <100）。

输出格式：

第 1 1 1 行：一个整数，为最高加分（结果不会超过int范围）。

第 2 2 2 行： n n n 个用空格隔开的整数，为该树的前序遍历。如果存在多种方案，则输出字典序最小的方案。

数据范围：

n < 30 n<30 n<30

输入样例：

5
5 7 1 2 10

  
 
    
  
  • 1
    • 
  
  • 2
    •

输出样例：

145
3 1 2 4 5

  
 
    
  
  • 1
    • 
  
  • 2
    •

思路分析

两个数组， f [ i ] [ j ] f[i][j] f[i][j] 为 d p dp dp 数组，即求 [ i , j ] [i,j] [i,j] 的最高分， g [ i ] [ j ] g[i][j] g[i][j] 存储 [ i , j ] [i,j] [i,j] 中的根节点，因为我们在枚举根节点的时候是从小到大的编号进行枚举的，并且在更新 f 、 g f、g f、g 数组只有在严格小于的情况下才会更新，故我们最后的前序遍历必定是符合字典序从小到大枚举的

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 35;

int n;
int w[N];
int f[N][N];  // 存储从 [i, j] 的最高分
int g[N][N];  // 存储从 [i, j] 的根节点

void print(int l, int r)
{
    if (l > r) return;
    cout << g[l][r] << ' ';
    print(l, g[l][r] - 1);   // 递归左子树
    print(g[l][r] + 1, r);   // 递归右子树
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> w[i];
    
    for (int len = 1; len <= n; len ++ )
        for (int l = 1; l + len - 1 <= n; l ++ )
        {
            int r = l + len - 1;
            if (len == 1) f[l][r] = w[l], g[l][r] = l;
            else
                for (int k = l; k <= r; k ++ )
                {
                    int left = k == l ? 1 : f[l][k - 1];
                    int right = k == r ? 1 : f[k + 1][r];
                    int score = left * right + w[k];
                    if (f[l][r] < score)
                    {
                        f[l][r] = score;
                        g[l][r] = k;
                    }
                }
        }
        
    cout << f[1][n] << endl;
    print(1, n);     // 递归输出前序遍历
    
    return 0;
}

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    • 
  
  • 18
    • 
  
  • 19
    • 
  
  • 20
    • 
  
  • 21
    • 
  
  • 22
    • 
  
  • 23
    • 
  
  • 24
    • 
  
  • 25
    • 
  
  • 26
    • 
  
  • 27
    • 
  
  • 28
    • 
  
  • 29
    • 
  
  • 30
    • 
  
  • 31
    • 
  
  • 32
    • 
  
  • 33
    • 
  
  • 34
    • 
  
  • 35
    • 
  
  • 36
    • 
  
  • 37
    • 
  
  • 38
    • 
  
  • 39
    • 
  
  • 40
    • 
  
  • 41
    • 
  
  • 42
    • 
  
  • 43
    • 
  
  • 44
    • 
  
  • 45
    • 
  
  • 46
    • 
  
  • 47
    • 
  
  • 48
    • 
  
  • 49
    • 
  
  • 50
    •

凸多边形的划分

题目要求

题目描述：

给定一个具有 N N N 个顶点的凸多边形，将顶点从 1 1 1 至 N N N 标号，每个顶点的权值都是一个正整数。

将这个凸多边形划分成 N − 2 N−2 N−2 个互不相交的三角形，对于每个三角形，其三个顶点的权值相乘都可得到一个权值乘积，试求所有三角形的顶点权值乘积之和至少为多少。

输入格式：

第一行包含整数 N N N，表示顶点数量。

第二行包含 N N N 个整数，依次为顶点 1 1 1 至顶点 N N N 的权值。

输出格式：

输出仅一行，为所有三角形的顶点权值乘积之和的最小值。

数据范围：

N ≤ 50 , N≤50, N≤50,
数据保证所有顶点的权值都小于 1 0 9 10^9 109

输入样例：

5
121 122 123 245 231

  
 
    
  
  • 1
    • 
  
  • 2
    •

输出样例：

12214884

  
 
    
  
  • 1
    •

思路分析

显然会爆 i n t int int，再定睛一看发现 l o n g long long l o n g long long 也会爆，果断 p y t h o n python python（不是，咳咳咳，果断高精度，高精度的算法讲解见博客：高精度运算，高精度的模板见博客：高精度算法模板，这里补充一个小 t i p s tips tips： w [ i ] {w[i]} w[i] 用了花括号，相当于是直接初始化成一个 v e c t o r vector vector，有关 v e c t o r vector vector 的讲解见博客：STL——vector

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 55;

int n;
int w[N];
vector<int> f[N][N];

bool cmp(vector<int> &a, vector<int> &b)
{
    if (a.size() != b.size()) return a.size() < b.size();
    for (int i = a.size() - 1; i >= 0; i -- )
        if (a[i] != b[i])
            return a[i] < b[i];
    return true;
}
vector<int> add(vector<int> a, vector<int> b)
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size() || i < b.size(); i ++ )
    {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    while (t) c.push_back(t % 10), t /= 10;
    return c;
}
vector<int> mul(vector<int> a, LL b)
{
    vector<int> c;
    LL t = 0;
    for (int i = 0; i < a.size(); i ++ )
    {
        t += b * a[i];
        c.push_back(t % 10);
        t /= 10;
    }
    while (t) c.push_back(t % 10), t /= 10;
    return c;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    //区间DP
    //此处初始状态f[l][l+1] = 0 初始就是空vector，不用额外设置
    for (int len = 3; len <= n; len ++ )
    {
        for (int l = 1, r; (r = l + len - 1) <= n; l ++ )
        {
            //初始化初始状态
            for (int k = l + 1; k < r; ++ k)
            {
                //w_l * w_k * w_r
                auto new_val = mul(mul({w[l]}, w[k]), w[r]); // {w[l]}可以直接初始化为一个vector
                //f[l][k] + f[k][r] + cost
                new_val = add(add(new_val, f[l][k]), f[k][r]);
                //f[l][r] = min(f[l][r], f[l][k] + f[k][r] + w_sum)
                if (f[l][r].empty() || cmp(new_val, f[l][r])) f[l][r] = new_val;
            }
        }
    }
    //输出最终答案
    auto res = f[1][n];
    for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]);
    puts("");

    return 0;
}

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    • 
  
  • 18
    • 
  
  • 19
    • 
  
  • 20
    • 
  
  • 21
    • 
  
  • 22
    • 
  
  • 23
    • 
  
  • 24
    • 
  
  • 25
    • 
  
  • 26
    • 
  
  • 27
    • 
  
  • 28
    • 
  
  • 29
    • 
  
  • 30
    • 
  
  • 31
    • 
  
  • 32
    • 
  
  • 33
    • 
  
  • 34
    • 
  
  • 35
    • 
  
  • 36
    • 
  
  • 37
    • 
  
  • 38
    • 
  
  • 39
    • 
  
  • 40
    • 
  
  • 41
    • 
  
  • 42
    • 
  
  • 43
    • 
  
  • 44
    • 
  
  • 45
    • 
  
  • 46
    • 
  
  • 47
    • 
  
  • 48
    • 
  
  • 49
    • 
  
  • 50
    • 
  
  • 51
    • 
  
  • 52
    • 
  
  • 53
    • 
  
  • 54
    • 
  
  • 55
    • 
  
  • 56
    • 
  
  • 57
    • 
  
  • 58
    • 
  
  • 59
    • 
  
  • 60
    • 
  
  • 61
    • 
  
  • 62
    • 
  
  • 63
    • 
  
  • 64
    • 
  
  • 65
    • 
  
  • 66
    • 
  
  • 67
    • 
  
  • 68
    • 
  
  • 69
    • 
  
  • 70
    • 
  
  • 71
    • 
  
  • 72
    • 
  
  • 73
    • 
  
  • 74
    • 
  
  • 75
    • 
  
  • 76
    • 
  
  • 77
    • 
  
  • 78
    • 
  
  • 79
    • 
  
  • 80
    •

文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。

原文链接：chen-ac.blog.csdn.net/article/details/123858072

【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
二叉树 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入