动态规划—区间DP(二)

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

加分二叉树

题目要求

题目描述:

image.png

输入格式:

第 1  行:一个整数 n ,为节点个数。

第 2  行:n  个用空格隔开的整数,为每个节点的分数(0 <  分数 < 100 )。

输出格式:

第 1 行:一个整数,为最高加分(结果不会超过int范围)。

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

数据范围:

n<30

输入样例:

5
5 7 1 2 10

输出样例:

145
3 1 2 4 5

思路分析

image.png

代码

#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;
}

凸多边形的划分

题目要求

题目描述:

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

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

输入格式:

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

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

输出格式:

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

数据范围:

N≤50,

数据保证所有顶点的权值都小于109

输入样例:

5
121 122 123 245 231

输出样例:

12214884

思路分析

image.png

代码

#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;
}




目录
相关文章
|
8月前
|
弹性计算 运维 API
阿里云服务器低价长效特惠,2核2G3M带宽40G云盘99元/年,新老用户同享!
2026年阿里云服务器推出低价长效特惠,其中99元特价云服务器(2核2G配置、3M带宽、40G高效云盘)成入门首选,体现普惠计算理念。该服务器适合个人开发者、小微企业官网等轻量应用。活动新老用户同享,但限购1台,可低价续费。此外,阿里云还有轻量应用服务器(38元/年)和通用算力型u1实例(199元/年)等丰富产品线。用户可根据技术能力、内存需求及长期成本选择最适合的方案。
|
数据采集 Web App开发 存储
Selenium库编写爬虫详细案例
Selenium库编写爬虫详细案例
|
存储 缓存 监控
美团面试:说说OOM三大场景和解决方案? (绝对史上最全)
小伙伴们,有没有遇到过程序突然崩溃,然后抛出一个OutOfMemoryError的异常?这就是我们俗称的OOM,也就是内存溢出 本文来带大家学习Java OOM的三大经典场景以及解决方案,保证让你有所收获!
7208 2
美团面试:说说OOM三大场景和解决方案? (绝对史上最全)
|
前端开发 Java 数据库连接
导出文件:使用Hutool导出数据为Excel文件
导出文件:使用Hutool导出数据为Excel文件
1770 0
导出文件:使用Hutool导出数据为Excel文件
【EDA】 Verdi 使用笔记
【EDA】 Verdi 使用笔记
5155 0
【EDA】 Verdi 使用笔记
|
10月前
|
JavaScript 搜索推荐 持续交付
手把手教你用 Vercel 免费部署 RSSHub
本文详细介绍如何使用Vercel免费部署RSSHub服务。通过Fork仓库、注册Vercel、导入项目并调整分支与Node.js版本配置,实现一键部署个性化的RSS订阅源,解决部署中常见的版本冲突问题,并提供注意事项与验证方法,助你快速搭建可公开访问的RSS服务。
1706 0
|
人工智能 Python
子曰-o1:网易有道开源国内首个分步式讲解推理模型,支持K12数学教学
子曰-o1是网易有道推出的国内首个分步式讲解推理模型,采用14B轻量级架构,专为消费级显卡设计,支持K12数学教学,提供精准的解题思路和答案。
1028 1
子曰-o1:网易有道开源国内首个分步式讲解推理模型,支持K12数学教学
|
Python
将NC栅格表示时间维度的数据提取出来的方法
【10月更文挑战第20天】本文介绍了如何使用 Python 和 R 语言以及 ArcGIS 软件提取 netCDF 文件中的时间维度数据。首先,通过安装和导入必要的库(如 Python 的 `netCDF4` 和 `numpy`,R 的 `ncdf4`),打开 netCDF 文件并读取时间变量。接着,详细展示了 Python 和 R 的示例代码,说明了如何读取和处理时间数据。最后,介绍了在 ArcGIS 中添加 netCDF 文件、启用时间属性并提取时间维度数据的方法。
978 1
|
Web App开发
成功解决Chrome浏览器 控制台下看不到接口信息的问题
这篇文章提供了解决Chrome浏览器控制台不显示接口信息问题的方法,包括检查过滤设置和确保“保留日志”开关已打开。
成功解决Chrome浏览器 控制台下看不到接口信息的问题