区间DP模型

目录

  • 环形石子合并
    • 思路
    • 代码实现
  • 能量项链
    • 代码实现
  • 加分二叉树
    • 思路
    • 代码实现
  • 凸多边形的划分
    • 代码实现
  • 棋盘分割
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例 #1
      • 样例输入 #1
      • 样例输出 #1
    • 佬的题解
    • 代码实现


环形石子合并

题目描述:

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

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

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

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

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

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

输出格式
输出共两行:

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

数据范围
1 ≤ n ≤ 200 1≤n≤200 1n200

输入样例:

4
4 5 9 4

输出样例:

43
54

思路

通过把原数组复制元素扩容到原来的两倍,这样便利起始位置 start [ 0 , n ) [0, n) [0,n),长度为 n n n,这样终止位置便为 [ 0 + n − 1 , n + n − 1 ) [0 + n - 1, n + n - 1) [0+n1,n+n1),用普通的石子区间DP遍历这样的几个 s t a r t start start 就可以得到最终答案。这样模拟起始位置相当于,模拟环状的各种断裂位置。

在这里插入图片描述


代码实现

import sys
from math import inf
input = sys.stdin.readline

n = int(input().strip())
nums = list(map(int, input().strip().split()))
nums = nums + nums

s = [0 for _ in range(2 * n + 1)]
for i in range(2 * n):
    s[i + 1] = s[i] + nums[i]
    

f = [[0 for _ in range(2 * n)] for _ in range(2 * n)]
for i in range(2 * n - 2, -1, -1):
    for j in range(i + 1, 2 * n - 1):
        f[i][j] = min(f[i][k] + f[k + 1][j] + s[j + 1] - s[i] for k in range(i, j))
print(min(f[start][start + n - 1] for start in range(n)))

f = [[0 for _ in range(2 * n)] for _ in range(2 * n)]
for i in range(2 * n - 2, -1, -1):
    for j in range(i + 1, 2 * n - 1):
        f[i][j] = max(f[i][k] + f[k + 1][j] + s[j + 1] - s[i] for k in range(i, j))
print(max(f[start][start + n - 1] for start in range(n)))

能量项链

题目描述:

M a r s Mars Mars 星球上,每个 M a r s Mars Mars 人都随身佩带着一串能量项链,在项链上有 N N N 颗能量珠。

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

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

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

如果前一颗能量珠的头标记为 m m m,尾标记为 r r r,后一颗能量珠的头标记为 r r r,尾标记为 n n n,则聚合后释放的能量为 m × r × n m×r×n m×r×n M a r s Mars Mars 单位),新产生的珠子的头标记为 m m m,尾标记为 n n n

需要时, M a r s Mars 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) (jk) 表示第 j , k j, k j,k 两颗珠子聚合后所释放的能量。则第 4 、 1 4、1 41 两颗珠子聚合后释放的能量为: ( 4 ⊕ 1 ) = 10 × 2 × 3 = 60 (4⊕1) = 10×2×3 = 60 (41)=10×2×3=60

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ( ( 4 ⊕ 1 ) ⊕ 2 ) ⊕ 3 ) = 10 × 2 × 3 + 10 × 3 × 5 + 10 × 5 × 10 = 710 ((4⊕1)⊕2)⊕3) = 10×2×3 + 10×3×5 + 10×5×10 = 710 ((41)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 , 1 ≤ E ≤ 2.1 × 1 0 9 4≤N≤100, 1≤E≤2.1×10^9 4N100,1E2.1×109

输入样例:

4
2 3 5 10

输出样例:

710

代码实现

与上一题的思路相同

import sys
input = sys.stdin.readline

n = int(input().strip())
nums = list(map(int, input().strip().split()))
nums = nums + nums

f = [[0 for _ in range(2 * n)] for _ in range(2 * n)]

for i in range(2 * n - 2, -1, -1):
    for j in range(i + 1, 2 * n):
        f[i][j] = max(f[i][k] + f[k + 1][j] + nums[i] * nums[j] * nums[k + 1] for k in range(i, j))

print(max(f[start][start + n - 1] for start in range(n)))

加分二叉树

题目描述:

设一个 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) t r e e tree tree 的最高加分

(2) 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 行:一个整数,为最高加分(结果不会超过 i n t int int 范围)。

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

数据范围:

n < 30 n < 30 n<30

输入样例:

5
5 7 1 2 10

输出样例:

145
3 1 2 4 5

思路

状态表示:
集合
f [ i ] [ j ] f[i][j] f[i][j] :从 i i i j j j 区间内,选一点 k k k 作为根节点,表示中序遍历是 w [ i ∼ j ] w[i∼j] w[ij] 的所有二叉树的集合。

属性
加分二叉树的 M a x Max Max 最大值

状态转移
任选节点 k k k,以 k k k 点为根构成的加分二叉树的值=它的左子树的最大加分值
× × × 右子树的最大加分值 + + + k k k点权值。
f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i ] [ k − 1 ] ∗ f [ k + 1 ] [ j ] + w [ k ] ) ( i < = k < = j ) f[i][j] = max(f[i][j], f[i][k - 1] * f[k + 1][j] + w[k]) (i <= k <= j) f[i][j]=max(f[i][j],f[i][k1]f[k+1][j]+w[k])(i<=k<=j)

注意若某个子树为空的情况,通过超出边界一些,来模拟子树为空的情况。


代码实现

import sys
input = sys.stdin.readline

n = int(input().strip())
w = list(map(int, input().strip().split()))

f = [[w[i] if i == j else 0 for j in range(n)] for i in range(n)]
path = [[i if i == j else 0 for j in range(n)] for i in range(n)]

for i in range(n - 1, -1, -1):
    for j in range(i + 1, n):
        for k in range(i, j + 1):
            ls = 1 if i == k else f[i][k - 1]
            rs = 1 if j == k else f[k + 1][j]
            val = ls * rs + w[k]
            if f[i][j] < val:
                f[i][j] = val
                path[i][j] = k


def out(l, r):
    if l > r:
        return
    print(path[l][r] + 1, end=' ')
    out(l, path[l][r] - 1)
    out(path[l][r] + 1, r)


print(f[0][-1])
out(0, n - 1)


凸多边形的划分

题目描述:

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

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

即:求所有三角形的顶点权值乘积之和的最小值。

输入格式:

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

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

输出格式:

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

数据范围:

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

输入样例:

5
121 122 123 245 231

输出样例:

12214884

代码实现

力扣原题

import sys
input = sys.stdin.readline

n = int(input().strip())
nums = list(map(int, input().strip().split()))

f = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n - 3, -1, -1):
    for j in range(i + 2, n):
        f[i][j] = min(f[i][k] + f[k][j] + nums[i] * nums[j] * nums[k] for k in range(i + 1, j))

print(f[0][-1])

棋盘分割

题目描述

将一个 8 × \times × 8 的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的部分继续如此分割,这样割了 ( n − 1 ) (n-1) (n1) 次后,连同最后剩下的矩形棋盘共有 n n n 块矩形棋盘。 (每次切割都只能沿着棋盘格子的边进行)

原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成 n n n 块矩形棋盘,并使各矩形棋盘总分的均方差最小。

均方差 σ = ∑ i = 1 n ( x i − x ˉ ) 2 n \sigma = \sqrt{ \frac{ \sum_{i=1}^n (x_i - \bar x)^2 } { n }} σ=ni=1n(xixˉ)2 ,其中平均值 x ˉ = ∑ i = 1 n x i n \bar x = \frac{\sum_{i=1}^n x_i}{n} xˉ=ni=1nxi , x i x_i xi 为第 i i i 块矩形棋盘的分。

请编程对给出的棋盘及 n n n ,求出 σ \sigma σ 的最小值。

输入格式

第一行为一个整数 n n n ($ 1 < n< 15 $)。

第二行至第九行每行为 8 8 8 个小于 100 100 100 的非负整数,表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

输出格式

仅一个数,为 σ \sigma σ (四舍五入精确到小数点后三位)。

样例 #1

样例输入 #1

3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3

样例输出 #1

1.633

佬的题解

佬的题解


代码实现

import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import inf, sqrt

n, m = int(input().strip()), 8
nums = [list(map(int, input().strip().split())) for _ in range(m)]
s = [[0] * (m + 1) for _ in range(m + 1)]

for i in range(m):
    for j in range(m):
        s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] + nums[i][j] - s[i][j]

ave = s[m][m] / n


def sum_grid(x1, y1, x2, y2):
    return (s[x2 + 1][y2 + 1] + s[x1][y1] - s[x2 + 1][y1] - s[x1][y2 + 1] - ave) ** 2


@lru_cache(maxsize=None)
def dfs(x1, y1, x2, y2, cnt):
    if cnt == n - 1:
        return sum_grid(x1, y1, x2, y2)
    res = inf

    for i in range(x1, x2):
        res = min(res, dfs(i + 1, y1, x2, y2, cnt + 1) + sum_grid(x1, y1, i, y2))
        res = min(res, dfs(x1, y1, i, y2, cnt + 1) + sum_grid(i + 1, y1, x2, y2))

    for i in range(y1, y2):
        res = min(res, dfs(x1, i + 1, x2, y2, cnt + 1) + sum_grid(x1, y1, x2, i))
        res = min(res, dfs(x1, y1, x2, i, cnt + 1) + sum_grid(x1, i + 1, x2, y2))

    return res


print("%.3f" % (round(sqrt(dfs(0, 0, 7, 7, 0) / n), 3)))

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/515554.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

前端(动态雪景背景+动态蝴蝶)

1.CSS样式 <style>html, body, a, div, span, table, tr, td, strong, ul, ol, li, h1, h2, h3, p, input {font-weight: inherit;font-size: inherit;list-style: none;border-spacing: 0;border: 0;border-collapse: collapse;text-decoration: none;padding: 0;margi…

C++从入门到精通——入门知识

1. C关键字(C98) C总计63个关键字&#xff0c;C语言32个关键字 2. 命名空间 在C/C中&#xff0c;变量、函数和后面要学到的类都是大量存在的&#xff0c;这些变量、函数和类的名称都将存在于全局作用域中&#xff0c;可能会导致很多冲突。使用命名空间的目的就是对标识符的名…

43.1k star, 免费开源的 markdown 编辑器 MarkText

43.1k star, 免费开源的 markdown 编辑器 MarkText 分类 开源分享 项目名: MarkText -- 简单而优雅的开源 Markdown 编辑器 Github 开源地址&#xff1a; https://github.com/marktext/marktext 官网地址&#xff1a; MarkText 支持平台&#xff1a; Linux, macOS 以及 Win…

中文Mistral模型介绍(Chinese-Mistral)——中文大语言模型

中文Mistral简介 Chinese-Mistral由清华大学地学系地球空间信息科学实验室开发。 该模型基于Mistral发布的Mistral-7B-v0.1训练得到。首先进行中文词表扩充&#xff0c;然后采用实验室提出的PREPARED训练框架&#xff08;under review&#xff09;在中英双语语料上进行增量预训…

C++Date类的实现

目录 前言&#xff1a; 1.显示日期 2.构造函数与获取某年某月的日期的函数 3.日期比较 4.日期加减天数 5.日期减日期 6.前置后置与-- 7.完整代码 8.测试 总结&#xff1a; 感谢支持&#xff01; 前言&#xff1a; 结合了前面的内容的学习&#xff0c;本篇来对之前的…

面试篇:杂乱篇

String s " "; 1. String类的常用方法有哪些&#xff1f; s.length()&#xff1a; 返回字符串长度s.substring()&#xff1a; 截取字符串s.split()&#xff1a; 分割字符串s.equlas()&#xff1a; 字符串比…

Ai智能生成图片神器,多种风格任你选,探索无限可能的视觉盛宴

在数字化浪潮中&#xff0c;图片已成为我们表达创意、传递情感、展示品牌的重要工具。然而&#xff0c;不是每个人都有专业的设计背景&#xff0c;也不是每个创作者都能轻松驾驭各种风格。这时&#xff0c;一款强大而灵活的AI智能生成图片神器应运而生&#xff0c;它将为你的创…

Vol.34 Good Men Project:一个博客网站,每月90万访问量,通过付费订阅和广告变现

今天给大家分享的案例网站是&#xff1a;Good Men Project&#xff0c;这是一个专门针对男性成长的博客网站&#xff0c;内容包括人际关系、家庭、职业发展等话题。 它的网址是&#xff1a;The Good Men Project - The Conversation No One Else Is Having 流量情况 我们先看…

【python实战】--提取所有目录下所有Excel文件指定列数据

系列文章目录 文章目录 系列文章目录前言一、问题描述二、python代码1.引入库 总结 前言 一、问题描述 需要提取指定路径下所有excel文件中指定一列数据&#xff0c;汇总到新文件&#xff0c;&#xff08;逐列汇总&#xff09; 二、python代码 1.引入库 代码如下&#xff08…

vue弹出的添加信息组件中 el-radio 单选框无法点击问题

情景描述:在弹出的添加信息的组件中的form中有一个单选框,单选框无法进行点击切换 原因如下: 单选框要求有个默认值,因为添加和更新操作复用同一个组件,所以我在初始化时对相关进行了判定,如果为空则赋初始值 结果这样虽然实现了初始值的展示,但是就是如此造成了单选框的无法切…

【MATLAB源码-第176期】基于matlab的16QAM调制解调系统频偏估计及补偿算法仿真,对比补偿前后的星座图误码率。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 在通信系统中&#xff0c;频率偏移是一种常见的问题&#xff0c;它会导致接收到的信号频率与发送信号的频率不完全匹配&#xff0c;进而影响通信质量。在调制技术中&#xff0c;QPSK&#xff08;Quadrature Phase Shift Keyin…

NIUSHOP完美运营版商城 虚拟商品全功能商城 全能商城小程序 智慧商城系统 全品类百货商城

完美运营版商城/拼团/团购/秒杀/积分/砍价/实物商品/虚拟商品等全功能商城 干干净净 没有一丝多余收据 还没过手其他站 还没乱七八走的广告和后门 后台可以自由拖曳修改前端UI页面 还支持虚拟商品自动发货等功能 挺不错的一套源码 前端UNIAPP 后端PHP 一键部署版本 源码免费…

基于SpringBoot+Vue前后端分离高校就业信息管理系统的设计与实现+毕业论文

介绍 随着中国大力发展教育事业&#xff0c;在校大学生的数量不断增多&#xff0c;导致大学毕业生的数量也不断增多&#xff0c;就业形势日趋严峻。开发一套符合就业形势的高校就业信息管理系统是非常必要的&#xff0c;这样既能提高就业管理部门的管理水平&#xff0c;又能通…

014——超声波模块驱动开发Plus(基于I.MX6uLL、SR04和poll机制)

目录 一、基础知识 二、分析为什么打印会影响中断 三、驱动程序 四、应用程序 五、验证及其它 一、基础知识 013——超声波模块驱动开发&#xff08;基于I.MX6uLL与SR04&#xff09;-CSDN博客 二、分析为什么打印会影响中断 asmlinkage __visible int printk(const ch…

Loadrunner的使用

Loadrunner的使用 选项公网测试地址&#xff1a;http://cfgjt.cn:8981/devt-web 用户名admin&#xff0c;密码11111111 1.Loadrunner介绍 ​ LoadRunner&#xff0c;是一种预测系统行为和性能的负载测试工具。通过模拟上千万用户实施并发负载及实时性能监测的方式来确认和查…

Ubuntu部署BOA服务器

BOA服务器概述 BOA是一款非常小巧的Web服务器&#xff0c;源代码开放、性能优秀、支持CGI通用网关接口技术&#xff0c;特别适合用在嵌入式系统中。 BOA服务器主要功能是在互联嵌入式设备之间进行信息交互&#xff0c;达到通用网络对嵌入式设备进行监控&#xff0c;并将反馈信…

【c/c++】深入探秘:C++内存管理的机制

&#x1f525;个人主页&#xff1a;Quitecoder &#x1f525;专栏&#xff1a;c笔记仓 朋友们大家好&#xff0c;本篇文章我们详细讲解c中的动态内存管理 目录 1.C/C内存分布2.C语言中动态内存管理方式&#xff1a;malloc/calloc/realloc/free3.c内存管理方式3.1new/delete对内…

LeetCode-199. 二叉树的右视图【树 深度优先搜索 广度优先搜索 二叉树】

LeetCode-199. 二叉树的右视图【树 深度优先搜索 广度优先搜索 二叉树】 题目描述&#xff1a;解题思路一&#xff1a;广度优先搜索解题思路二&#xff1a;深度优先搜索解题思路三&#xff1a;0 题目描述&#xff1a; 给定一个二叉树的 根节点 root&#xff0c;想象自己站在它…

股权激励和期权激励对比辨析

文章目录 概念定义 收益方式 风险评估 应用和分析 股权激励和期权激励&#xff0c;两者的区别是什么&#xff0c;本文就来梳理对比一下。 概念定义 股权激励&#xff0c;是指上市公司以本公司股票为标的&#xff0c;对其董事、高级管理人员及其他员工进行的长期性激励。取得…

微服务(基础篇-008-es、kibana安装)

目录 05-初识ES-安装es_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1LQ4y127n4?p81&vd_source60a35a11f813c6dff0b76089e5e138cc 1.部署单点es 1.1.创建网络 1.2.加载镜像 1.3.运行 2.部署kibana 2.1.部署 2.2.DevTools 3.安装IK分词器 3.1.在线安装ik…