2829专题

Day 9:2829. k-avoiding 数组的最小总和

Leetcode 2829. k-avoiding 数组的最小总和 给你两个整数 n 和 k 。 对于一个由 不同 正整数组成的数组,如果其中不存在任何求和等于 k 的不同元素对,则称其为 k-avoiding 数组。 返回长度为 n 的 k-avoiding 数组的可能的最小总和。 n 个不同正整数的最小总和,那就是从 1 到 n 的总和,但是还有一个要求就是不存在任何求和等于 k

HDU 2829 [Lawrence] DP斜率优化

解题思路 首先肯定是考虑如何快速求出一段铁路的价值。\[ \sum_{i=1}^k \sum_{j=1, j\neq i}^kA[i]A[j]=(\sum_{i=1}^kA[i])^2-\sum_{i=1}^kA[i]^2 \] 那么我们要维护如下两个东西,就可以在\(O(1)\)内求出一段铁路的价值了。 for( LL i = 1; i <= N; ++i ) Sum[ i ] = Sum[