题目描述：
给你一个长度为 n 下标从 0 开始的整数数组 nums 和一个 正奇数 整数 k 。
x 个子数组的能量值定义为 strength = sum[1] * x - sum[2] * (x - 1) + sum[3] * (x - 2) - sum[4] * (x - 3) + ... + sum[x] * 1 ，其中 sum[i] 是第 i 个子数组的和。更正式的，能量值是满足 1 <= i <= x 的所有 i 对应的 (-1)i+1 * sum[i] * (x - i + 1) 之和。
你需要在 nums 中选择 k 个 不相交子数组 ，使得 能量值最大 。
请你返回可以得到的 最大能量值 。
注意，选出来的所有子数组 不 需要覆盖整个数组。
数据范围：
$1\le n \le 10^4, 1\le k \le n, 1\le n \times k \le 10^6, 1\le nums[i] \le 10^9$
题解：
数据范围暗示需要 $n\times k$ 的复杂度。
子数组的和需要使用前缀和得到。可以预先处理出 $preSum[i], i \in [1, n]$
假设 $dp[i][j]$ 表示从 $[1, \cdots,i]$ 划分为 $j, j\in[1, i]$ 段的最大能量值，则
如果不取 $nums[i]$ 的话，直接跳过，就是 $dp[i - 1][j]$ 。如果考虑取 $nums[i]$ 的话，就需要枚举上一段的终点了。假设上一段的终点是 $p$ ，上一段划分了 $j - 1$ 个子数组，那么 $p \in [j - 1, i - 1]$ 。
需要注意的是 $i$ 和 $j$ 之间也是有范围约束的。如果先枚举 $i$ ，那么 $j \in [1, min(i, k)]$ 。如果先枚举 $j$ ，那么 $i \in [j, n + j - k]$ ，因为 $n - i \ge k - j$ ，需要保证后面 $n - i$ 个元素能划分出来 $k - j$ 段。
但是三重循环的话应该会超时。
考虑对递推公式转化一下
看做两项作差的形式，那么只有后一项与 $p$ 有关，其中 $p \in [j - 1, i - 1]$ 。可以考虑维护 $dp[p][j - 1] - tmp \times preSum[p] \times (k - j + 1)$ 的最大值，因为 $p$ 最大是 $i - 1$ 。每增加一下 $i$ ，都需要更新一下最大值。
如果先枚举 $j, j\in [1, k]$ ，再枚举 $i, i\in [j, n + j - k]$ 。可以考虑在循环 $i, i\in [j, n + j - k]$ 之前，先用循环求出 $i \in [0, j - 1]$ ， $maxx = dp[i][j - 1] - tmp \times preSum[i] \times (k - j + 1)$ 。
然后再循环 $i$ ，在循环内部，每次更新 $dp[i][j]$ 之后，需要更新一下 $maxx$ 。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
long long maximumStrength(vector<int> &nums, int k)
{
int n = nums.size();
vector<long long> preSum(n + 1);
for (int i = 1; i <= n; ++i)
preSum[i] = preSum[i - 1] + nums[i - 1];
vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, -INF_LL));
dp[0][0] = 0;
for (int i = 0; i <= n; ++i)
dp[i][0] = 0;
for (int kk = 1; kk <= k; ++kk)
{
for (int i = kk; i <= n - k + kk; ++i)
{
for (int j = max(kk - 1, 1); j <= i; ++j)
{
int tmp = (kk & 1 ? 1 : -1);
dp[i][kk] = max(dp[i][kk], max(dp[i - 1][kk], dp[j - 1][kk - 1] + tmp * (preSum[i] - preSum[j - 1]) * (k - kk + 1)));
}
}
}
return dp[n][k];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
long long maximumStrength(vector<int> &nums, int k)
{
int n = nums.size();
vector<long long> preSum(n + 1);
for (int i = 1; i <= n; ++i)
{
preSum[i] = preSum[i - 1] + nums[i - 1];
}
vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, -INF_LL));
dp[0][0] = 0;
for (int i = 0; i <= n; ++i)
dp[i][0] = 0;
for (int kk = 1; kk <= k; ++kk)
{
long long maxx = -INF_LL;
int tmp = (kk & 1 ? 1 : -1);
for (int i = 0; i < kk; ++i)
{
maxx = max(maxx, dp[i][kk - 1] - tmp * preSum[i] * (k - kk + 1));
}
for (int i = kk; i <= n - k + kk; ++i)
{
dp[i][kk] = max(dp[i][kk], max(dp[i - 1][kk], maxx + tmp * preSum[i] * (k - kk + 1)));
maxx = max(maxx, dp[i][kk - 1] - tmp * preSum[i] * (k - kk + 1));
}
}
return dp[n][k];
}
};
|