AcWing 299. 裁剪序列(单调队列优化dp)
原题链接
困难
作者:
小小_88
,
2022-09-16 23:23:19
,
所有人可见
,
阅读 772
裁剪序列
C++ 代码
/*
本题有一个类似的版本,曾试过用倍增来做,这里考虑用 dp 来做。
设 f[i] 表示前 i 个数分成若干段,在满足每段中所有数的和不超过 m 的前提下,各段的最大值之和最小是多少
枚举最后一段的情况来进行转移,很容易得出以下的状态转移方程:
f[i] = min{ f[j] + max{ a[k] } (j + 1 <= k <= i) } (0 <= j < i && sum{ a[k] } <= m (j + 1 <= k <= i))
若采用枚举决策 j 的方法,时间复杂度为 O(n^2),会超时,需要优化,但是该方程似乎很难进行优化,
因为 max{ a[k] } (j + 1 <= k <= i) 不容易用一个简单的多项式来表示,不容易找到特性如单调性。
dp 的一种常用优化思想就是及时排除不可能的决策,因此考虑一个决策 j 何时是必要的
定理:
在上述方程中,若 j (0 <= j < i) 可能成为最优决策,则除了 sum{ a[k] } <= m (j + 1 <= k <= i) 外,
一定还满足以下两个条件之一:
1. a[j] = max{ a[k] } (j <= k <= i)
2. sum{ a[k] } > m (j <= k <= i) (即 j 是满足 sum{ a[k] } <= m (j + 1 <= k <= i) 的最小的 j)
证明:
反证法。假设两个条件都不满足,即 a[j] < max{ a[k] } (j <= k <= i) && sum{ a[k] } <= m (j <= k <= i)。
由此可知 max{ a[k] } (j <= k <= i) == max{ a[k] } (j + 1 <= k <= i)。另外,f[] 显然具有单调性,即
f[j - 1] <= f[j] (多一个数,答案只会变大不会变小)。
于是,f[j - 1] + max{ a[k] } (j <= k <= i) <= f[j] + max{ a[k] } (j + 1 <= k <= i),这里的含义就是
决策 j - 1 比 j 更优,而决策的取值范围是 0 <= j < i,j - 1 比 j 更容易满足这个条件,所以这里与 j
可能成为最优决策矛盾,故假设不成立。
证毕。
定理中的第 2 个条件比较简单,只需预处理出对于每个 i,满足 sum{ a[k] } <= m (j + 1 <= k <= i) 的最小的 j,
记为 c[j],在计算 f[i] 时,从 c[i] 进行一次状态转移即可,下面单独讨论满足定理中第 1 个条件的决策 j
的维护方法。
根据定理,当一个新的决策 j2 插入候选集合时,若候选集合中已有的决策 j1 满足条件 j1 < j2 并且 a[j1] < a[j2],
则 j1 就是无用策略,可以直接排除。
综上所述,我们可以维护一个决策点 j 单调递增、数值 a[j] 单调递减的队列,只有该队列中的元素才可能成为最优决策。
光这样还不够,该队列只是一个 a[j] 单调递减的队列,关于转移方程等式右边的 f[j] + max{ a[k] } (j + 1 <= k <= i)
并没有单调性。所以我们不能简单的取队头作为最优决策,而是再加一个额外的数据结构,如二叉堆,二叉堆与单调队列
保存相同的候选集合,该插入时一起插入,该删除时一起删除,只不过单调队列以 a[j] 递减作为比较大小的依据,
二叉堆以 f[j] + max{ a[k] } (j + 1 <= k <= i) 作为比较大小的依据,保证能快速的在候选集合中查询最值,
我们称这种操作为 "二叉堆与单调队列建立了映射关系",但是二叉堆要想跟着队列一起删除元素需要用 "懒惰删除",
这里直接采用平衡树(multiset)来实现,效果是一样的
最后,关于 max{ a[k] } (j + 1 <= k <= i) 的计算有两种方法,第一种是按照区间最值问题,直接用 ST 算法预处理,
支持 O(1) 查询。第二种是仔细挖掘本题中单调队列的性质,可以发现队列中某一项的 max{ a[k] } (j + 1 <= k <= i)
的结果其实就是队列中下一个元素的 a 值。
在整个算法中,每个 j 至多在单调队列和平衡树中插入和删除一次,故时间复杂度为 O(nlogn)
*/
#include <iostream>
#include <cstring>
#include <set>
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
LL m;
int a[N];
LL f[N];
int c[N]; //c[j] 表示满足 sum{ a[k] } <= m (j + 1 <= k <= i) 的最小的 j
int q[N]; //单调队列,队首 q[j] 表示 max{ a[k] } (j <= k <= i)
multiset<LL> S; //平衡树,存储 f[j] + max{ a[k] } (j + 1 <= k <= i)
//将队列 q[j] 和平衡树存储的 f[q[j]] + a[q[j + 1]] 之间建立映射关系
int main()
{
scanf("%d%lld", &n, &m);
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
if(a[i] > m) //如果存在 > m 的数,不可能成功分段
{
puts("-1");
return 0;
}
}
//预处理 c[i]
LL sum = 0; //记录 sum { a[k] } (j + 1 <= k <= i)
for(int i = 1, j = 0; i <= n; i++)
{
sum += a[i];
//若 sum { a[k] } > m (j + 1 <= k <= i),则需去掉 a[j + 1],并后移 j
while(sum > m) sum -= a[j + 1], j++;
c[i] = j; //到这说明找到了最小的 j,使得 sum { a[k] } <= m (j + 1 <= k <= i)
}
//单调队列优化 dp
int hh = 0, tt = -1; //初始化队列
for(int i = 1; i <= n; i++)
{
/*
注意,状态转移方程是 f[i] = f[j] + a[...],这里 j 可能成为最优策略的条件有两种,条件之一是
a[j] = max{ a[k] } (j <= k <= i),因此 j 可以直接就是 q[hh],那么对应的 a[...] 就是 q[hh + 1]。
平衡树中存储的状态就都是这个类型的,然后每次从平衡树中取最小值进行转移。条件之二是 j = c[i],
这时 a[...] 就是 c[i] 之后最大的 a[],即 q[hh],这种类型的状态在队首排除完不合法的元素后即可进行转移
*/
while(hh <= tt && q[hh] < c[i])
{
S.erase(f[q[hh]] + a[q[hh + 1]]); //删除平衡树中对应的 f[j] + sum { a[k] } (j + 1 <= k <= i)
hh++; //队列中删除
}
while(hh <= tt && a[q[tt]] <= a[i])
{
//注意,删除队尾时,对于 tt - 1 位置的 f[q[tt - 1]] + a[q[tt]] 来说 a[q[tt]] 已经不存在,
//换成了 a[i],所以对应的旧值也已经没有意义,需要删除旧值,然后在插入 a[i] 时将新值放回去
S.erase(f[q[tt - 1]] + a[q[tt]]); //删除平衡树中对应的 f[j] + sum { a[k] } (j + 1 <= k <= i)
tt--; //队列中删除
}
if(hh <= tt) S.insert(f[q[tt]] + a[i]); //用新值替换删去的旧值
q[++tt] = i; //将 i 加入队列
f[i] = f[c[i]] + a[q[hh]]; //条件之二 状态转移
if(!S.empty()) f[i] = min(f[i], *S.begin()); //条件之一 状态转移
}
printf("%lld\n", f[n]);
return 0;
}