【题解】HackerRank - Summing Pieces
题目
https://www.hackerrank.com/challenges/summing-pieces
题意
给定一列数,分割成任意多段,某一种分法的值为每一段的数字和和段长之积之和,求所有方案的值的总和。
题解
- 首先写一个会超时的O(n2)的算法
1 | FOR(i, 1, n + 1) |
- 发现n个数有2n − 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)) - 对于某一个位置
- 如果有一端在头或者尾,则被计算的次数为2n − l − 1
- 如果在中间,则被计算的次数为2n − l − 2
1 |
|