K 个不相交子数组的最大能量值

题目

输入长度为 \(n\) 的整数数组 \(nums\) 和正奇数 \(k\)，输出从数组中选择 \(k\) 个不相交的子数组，能够得到的最大得分。\(k\) 个子数组的得分为 \(\sum_{i=1}^{k}(-1)^{i+1}\times sum[i]\times (k-i+1)\)，其中 \(sum[i]\) 表示第 \(i\) 个子数组中元素之和。

数据范围：\(1\leq n\leq 10^{4}\)，\(-10^{9}\leq nums[i]\leq 10^{9}\)，\(1\leq k\leq n\)，\(1\leq n\times k\leq 10^{6}\)。

思路

定义 \(dp[i][r]\) 表示从区间 \([0,r-1]\) 选择 \(i\) 个不相交子数组，能够得到的最大得分。对于元素 \(nums[r-1]\)，我们有选或者不选两种情况，状态转移方程如下：

初始时，对于所有 \(0\leq i\leq n\)，有 \(dp[0][i]=0\)，其他值初始化为负无穷。使用上述转移方程，时间复杂度为 \(O(kn^{2})\)。可以对其变形，将时间复杂度优化为 \(O(kn)\)，详细参见灵神的题解。小羊的题解使用的是另一种做法，似乎更简洁，但是看不太懂啊。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public long maximumStrength(int[] nums, int k) {
        int n = nums.length;
        long[] sum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }

        long[][] dp = new long[k + 1][n + 1];
        for (int i = 1; i <= k; i++) {
            Arrays.fill(dp[i], Long.MIN_VALUE);
        }

        for (int i = 0; i < k; i++) {
            long max = Long.MIN_VALUE;
            int w = (2 * (i & 1) - 1) * -1 * (k - i);
            for (int r = i; r < n - (k - i - 1); r++) {
                max = Math.max(max, dp[i][r] - sum[r] * w);
                dp[i + 1][r + 1] = Math.max(dp[i + 1][r], sum[r + 1] * w + max);
            }
        }
        return dp[k][n];
    }
}

给定操作次数内使剩余元素的或值最小

题目

输入长度为 \(n\) 的整数数组 \(nums\) 和整数 \(k\)，输出执行至多 \(k\) 次操作之后，将数组中所有剩余元素按位或的最小值。每次操作可以选择一个下标 \(i\)，满足 \(0\leq i<n\)，将 \(nums[i]\) 和 \(nums[i+1]\) 替换为它们按位与的结果。注意，是两个数替换为一个数。

数据范围：\(1\leq n\leq 10^{5}\)，\(0\leq nums[i]<2^{30}\)，\(0\leq k< n\)。

思路

要使按位或的结果最小，肯定是从高位到低位消除。但是高位消除的方式会影响低位消除的方式，它们是相关的，不能单独计算每一位的操作次数。如果暴力枚举所有位的组合，会有 \(2^{30}\) 种情况，肯定会超时。如何计算？其实，只需要考虑从高位到低位的组合方式。从高位开始，能够消除的位总是应该被消除，然后判断加上更低的一位是否能被消除（保留相关性），如果不能，则该低位就永远不会被消除，以此类推。那么如何判断某个位的组合是否能被消除？从前往后遍历数组，贪心的将数组分割为若干按位与结果为 0 的子数组（假设为 \(m\)），则当前组合消除所需的操作次数为 \(n-m\)。具体可以看下灵茶山的题解和小羊的题解。

移除后集合的最多元素数

题目

输入长度为偶数 \(n\) 的数组 \(a\) 和 \(b\)，输出从 \(a\) 和 \(b\) 中分别选择一半元素构成的集合的最大大小。

数据范围：\(1\leq n\leq 2\times 10^{4}\)。

思路

要使集合尽可能大，肯定优先选择除 \(a\) 和 \(b\) 交集以外的元素，假设分别为 \(x\) 和 \(y\)，则可以选择 \(s=\min(x,\frac{n}{2})+\min(y,\frac{n}{2})\) 个不同元素。此时还有 \(n-s\) 个元素待选，假设交集的大小为 \(z\)，则答案为 \(s+\min(n-s,z)\)。

执行操作后的最大分割数量

题目

输入长度为 \(n\) 的字符串 \(s\) 和一个整数 \(k\)，输出至多改变一个字符时，执行操作能够得到的最大分割数。每次操作可以分割 \(s\) 的最多包含 \(k\) 个不同字符的最长前缀。

数据范围：\(1\leq n\leq 10^{4}\)，\(1\leq k\leq 26\)。

思路

首先，很容易想到暴力做法，枚举每个位置的所有改变情况，然后通过遍历求分割数，时间复杂度为 \(O(n^{2}|\Sigma|\log{|\Sigma|})\)。显然，可以优化的部分就是最后遍历求分割数的 \(O(n\log{|\Sigma|})\)。然后观察修改字符相比不修改字符会产生什么变化，可以发现修改字符所在的分割段的长度可能发生变化，而前缀的分割数是固定的。可以想到预处理原字符串每个位置 \(i\) 的后缀分割数，问题就剩下如何快速求得修改字符所在段的右端点。由于字符数随着长度的增加而增加，所以可以通过二分求得该段的右端点，这还需要花费 \(O(n|\Sigma|)\) 的时间提前预处理出字符数的前缀和。最后，分割数为前缀 + 中间 + 后缀的段数。代码实现时，还有很多其他细节需要注意，强烈建议自己实现一下。