ACWing-331-干草堆
题意
输入一个数组是否可以分割为几个小段,使的这些小段之和单调不增。
解法
首先,我们将区间整个翻转,那么原题中的单调不增则变为单调不减。
我们记录答案为F(i , j)
表示最后一段是区间 (j , i]
的最大高度。由此,我们得到状态转移方程
$$
F(i , j) = \max\limits_{k<j<i,S_i-S_j\ge S_{j-1}-S_{k}} \{F(j,k)+1\}
$$
枚举这个区间的复杂度大约为 $O(N^3)$
记录 top[i]
为最后一段选择 (j, i]
时候最上面一层的宽度 。那么因此我们的答案可以变为如下的状态转移的方程。
$$ F(i)=\max\limits_{i<j,S_i-S_j \ge top[j]} F(j)+1 $$
那么对于一些满足是我们当前最优高度的 j
我们希望 top[i]
越小越好,因此我们的 j
也就是越大越优。由于我们的条件 S[i]-S[j]>=top[j] ==> S[i]>=S[j]+top[j]
因此我们只需要找到最大的 j
即可。那么我们的方程得到了初步的化简。时间复杂度最坏的情况为 $O(N^2)$
for (int i = 1 ; i <= n ; i ++ ) {
int j ;
for (j = i - 1 ; j != -1 ; j -- ) /*1*/
if(S[i] >= S[j] + top[j]) break; /*2*/
F[i] = F[j] + 1;
top[i] = S[i] - S[j];
}
当然,数据太水了,这个甚至能过。hhhhh,结尾贴一下完整的代码。
我们不妨再仔细观察一下上面的代码,我们发现 1、2 号语句中终止的条件为第一个 S[i]>=S[j]+top[j]
不妨思考一下,是不是我们可以维护一个东西让这个里面永远存下当前的最小的 S[j]+top[j]
呢。OK,那么我们这个可以使用单调队列来维护该最小值。
q[0] = 0;
for (int i = 1, head = 0, tail = 0; i <= n; i++) {
while (head <= tail && S[q[head]] + top[head] <= S[i]) head++;
// -- 最后弹出对列的数,就是最符合 S[i] >= S[j] + top[j]
// -- 因为我们把最符合条件的都弹走了嘛 ~
// -- 是因为 S[i] 是单增的所有我们就可以放心大胆的弹。
F[i] = F[q[head - 1]] + 1;
top[i] = S[i] - S[q[head - 1]];
while (head <= tail && S[q[tail]] + top[q[tail]] >= S[i] + top[i]) tail--;
q[++tail] = i;
}
那么答案,如下
$O(N)$
#include <iostream>
#include <vector>
using namespace std;
int main() {
using LL = long long;
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<LL> S(n + 1), q(n + 1), F(n + 1), top(n + 1);
S[0] = q[0] = F[0] = top[0] = 0;
for (int i = n; i >= 1; i--) cin >> S[i];
for (int i = 1; i <= n; i++) S[i] += S[i - 1];
q[0] = 0;
for (int i = 1, head = 0, tail = 0; i <= n; i++) {
while (head <= tail && S[q[head]] + top[q[head]] <= S[i]) head++;
F[i] = F[q[head - 1]] + 1;
top[i] = S[i] - S[q[head - 1]];
while (head <= tail && S[q[tail]] + top[q[tail]] >= S[i] + top[i])
tail--;
q[++tail] = i;
}
cout << F[n] << '\n';
return 0;
}
$O(N^2)$
#include <iostream>
#include <vector>
using namespace std;
int main() {
using LL = long long;
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<LL> S(n + 1), q(n + 1), F(n + 1), top(n + 1);
S[0] = q[0] = F[0] = top[0] = 0;
for (int i = n; i >= 1; i--) cin >> S[i];
for (int i = 1; i <= n; i++) S[i] += S[i - 1];
for (int i = 1; i <= n; i++) {
int j;
for (j = i - 1; j != -1; j--)
if (S[i] >= S[j] + top[j]) break;
F[i] = F[j] + 1;
top[i] = S[i] - S[j];
}
cout << F[n] << '\n';
return 0;
}