【题解】HackerRank - Summing Pieces
题目
https://www.hackerrank.com/challenges/summing-pieces
题意
给定一列数,分割成任意多段,某一种分法的值为每一段的数字和和段长之积之和,求所有方案的值的总和。
题解
- 首先写一个会超时的$O(n^2)$的算法
1 | FOR(i, 1, n + 1) |
- 发现$n$个数有$2^{n-1}$种方案(可以理解为有$n-1$个空隙,每个空隙都可以选择是否插板)
- 根据数据范围,这道题目要求$O(n)$的算法
官方题解
- https://www.hackerrank.com/challenges/summing-pieces/editorial
- 将 dp[i] 的和式进行变形,利用前缀和快速转移
题解
- 考虑长度为 l 的一段
- 它所有的位置覆盖每一个数的次数是这样的:
1, 2, … , m - 1, m, m, … , m, m - 1, …, 2, 1 (m = min(l, n + 1 - l)) - 对于某一个位置
- 如果有一端在头或者尾,则被计算的次数为$2^{n-l-1}$
- 如果在中间,则被计算的次数为$2^{n-l-2}$
1 |
|