考点
思路
比较难的一道综合题，为什么评级只是中等？
根据题意是划分DP裸题，可以得到下面的超时代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
static const int maxn = 5e4 + 5, mod = 1e9 + 7, inf = 0x3f3f3f3f,
neg = 0xcfcfcfcf;
int countPartitions(vector<int>& nums, int k) {
long long f[maxn];
int n = nums.size();
memset(f, 0, sizeof(f));
f[0] = 1;
for (int i = 1; i <= n; ++i) {
int mx = neg, mi = inf;
for (int j = i; j >= 1; --j) {
mx = max(mx, nums[j - 1]), mi = min(mi, nums[j - 1]);
if (mx - mi > k) break;
f[i] = (f[i]+f[j - 1])%mod;
}
}
return f[n];
}
};
|
难点在于优化：
首先可以发现，对于任何一个区间，在包含一个新的元素时，新区间它的k有且只有三种可能：
- 保持不变，即没有改变
max和min
- 改变了
max，k变大
- 改变了
min，k变大
综上，k只可能是不变或者是变大
那么对于当前的i，只需要暴力地一直向左扩展枚举连续区间，直到不满足条件即可退出
这也是上面的暴力DP的解决方案
假设现在已知f[i - 1]，它的最大向左扩展连续区间为[L, i - 1]，
那么f[i - 1] = f[L - 1] + ... + f[i - 2]
考虑转移到f[i]时的情况，对于i而言，它的最大向左扩展连续区间为[L, i]，或者向右缩小，不可能反向向左增大
道理很简单，对于i - 1而言，[L, i - 1]已经是极限，如果再加上一个i变成[L, i]，则说明i对该区间的max和min并无贡献，没有理由还会向左增大
明白这一层后，就可以用前缀和+单调队列进行优化了：
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
| class Solution {
public:
static const int maxn = 5e4 + 5, mod = 1e9 + 7, inf = 0x3f3f3f3f,
neg = 0xcfcfcfcf;
int countPartitions(vector<int>& nums, int k) {
deque<int> mx, mi;
int l = 1, f[maxn], n = nums.size();
long long s = 0;
memset(f, 0, sizeof(f));
f[0] = 1;
for (int i = 1; i <= n; ++i) {
int x = nums[i - 1];
while (!mi.empty() && nums[mi.back() - 1] >= x) mi.pop_back();
mi.push_back(i);
while (!mx.empty() && nums[mx.back() - 1] <= x) mx.pop_back();
mx.push_back(i);
s = (s + f[i - 1]) % mod;
while (!mx.empty() && !mi.empty() &&
nums[mx.front() - 1] - nums[mi.front() - 1] > k) {
s = (s - f[l - 1] + mod) % mod;
l++;
while (!mx.empty() && mx.front() < l) mx.pop_front();
while (!mi.empty() && mi.front() < l) mi.pop_front();
}
f[i] = s;
}
return f[n];
}
};
|
注意，上面当中的
1
2
| while (!mx.empty() && mx.front() < l) mx.pop_front();
while (!mi.empty() && mi.front() < l) mi.pop_front();
|
完全可以改成下面
1
2
| if (!mx.empty() && mx.front() < l) mx.pop_front();
if (!mi.empty() && mi.front() < l) mi.pop_front();
|
因为本题的单调队列保存的下标一定是单调递增的，而其对应的值也一定是单调递减/递增的，
向右缩减区间要删除队列中的无效点时，它要么不存在队列，要么一定在队头，不可能在队中