目录
- 环形石子合并
- 思路
- 代码实现
- 能量项链
- 代码实现
- 加分二叉树
- 思路
- 代码实现
- 凸多边形的划分
- 代码实现
- 棋盘分割
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- 样例输入 #1
- 样例输出 #1
- 佬的题解
- 代码实现
环形石子合并
题目描述:
将 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
输出样例:
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+n−1,n+n−1),用普通的石子区间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) (j⊕k) 表示第 j , k j, k j,k 两颗珠子聚合后所释放的能量。则第 4 、 1 4、1 4、1 两颗珠子聚合后释放的能量为: ( 4 ⊕ 1 ) = 10 × 2 × 3 = 60 (4⊕1) = 10×2×3 = 60 (4⊕1)=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 ((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 , 1 ≤ E ≤ 2.1 × 1 0 9 4≤N≤100, 1≤E≤2.1×10^9 4≤N≤100,1≤E≤2.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[i∼j] 的所有二叉树的集合。
属性
加分二叉树的
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][k−1]∗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 N−2 个互不相交的三角形,对于每个三角形,其三个顶点的权值相乘都可得到一个权值乘积,试求所有三角形的顶点权值乘积之和至少为多少。
即:求所有三角形的顶点权值乘积之和的最小值。
输入格式:
第一行包含整数 N N N,表示顶点数量。
第二行包含 N N N 个整数,依次为顶点 1 1 1 至顶点 N$ 的权值。
输出格式:
输出仅一行,为所有三角形的顶点权值乘积之和的最小值。
数据范围:
N ≤ 50 N≤50 N≤50,数据保证所有顶点的权值都小于 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) (n−1) 次后,连同最后剩下的矩形棋盘共有 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 }} σ=n∑i=1n(xi−xˉ)2 ,其中平均值 x ˉ = ∑ i = 1 n x i n \bar x = \frac{\sum_{i=1}^n x_i}{n} xˉ=n∑i=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)))