## 487B

Posted on 28 Nov 2014
dynamic programming two pointers monotonic queue

### Description

Given a sequence of numbers of length $n$. ($1 \leq n \leq 10^5$) It require us to split the sequence into several substrip, and the difference between the maximum value and minimum value in each strip is no greater than $l$, and the length of each substrip must be greater than $s$. Output the minimal number of strip it could be divided into.

### Tutorial

Use dynamic programming to solve the problem. Let $f[i]$ denote the minimal number of pieces that the first $i$ numbers can be split into. $g[i]$ denote the least possible left boarder of substrip whose right border is $i$ which satisfies the condition. Then $f[i] = min(f[k]) + 1$, where $g[i] ≤ k ≤ i - l$.

One possible way to calculate $g[i]$ is to use monotonic queue which can be done in $O(n)$. But it is hard to implement, since we need to maintain 2 monotonic queues to for the maximal and minimal value, especially when it comes to the pop operation.

Here we have a alternative way to do this, multiset. Multiset is a STL container which have the same function of STL set, however, it can store multiple items of the same value. We can insert and erase a element by $O(logN)$, which is slower than the push and pop of monotonic queue which is $O(1)$. Quest any element in multiset (e.g. maximum, minimum) in $O(1)$. (I cannot believe that) It can be used as follows.

multiset<E> m;
m.insert(a);	//insert a into the multiset
m.erase(m.lower_bound(a));	//delete a from the multiset
*m.begin();	//the minimum element
*(--m.end());	//the maximum element


With so easy to access the maximum and minimum, we can finish the task of calculating $g[i]$ with a process of two pointers, which is to push the right boarder by 1 and to push the left boarder until it satisfies the condition.

We can also use either monotonic queue or multiset to calculate $f[i]$, because its also a task of finding the minimal between the two pointers.

### Solution

#include <cstdio>
#include <cmath>
#include <set>
using namespace std;

#define MAX_N 100005
#define D(x)
#define INF 0x3f3f3f3f

int n, s, max_diff;
int seq[MAX_N];
int f[MAX_N], g[MAX_N];

void input()
{
scanf("%d%d%d", &n, &max_diff, &s);
for (int i = 0; i < n; i++)
{
scanf("%d", &seq[i]);
}
}

int work()
{
multiset<int> multi_set;
int left = 0;
for (int i = 0; i < n; i++)
{
multi_set.insert(seq[i]);
while (!multi_set.empty())
{
int min_val = *multi_set.begin();
int max_val = *(--multi_set.end());
D(printf("	min=%d\n", min_val));
D(printf("	max=%d\n", max_val));
if (max_val - min_val <= max_diff)
{
break;
}
D(printf("	left=%d\n", left));
multi_set.erase(multi_set.lower_bound(seq[left]));
left++;
}
g[i] = left;
D(printf("g[%d]=%d\n", i, g[i]));
}

multi_set.clear();
f[0] = 0;
for (int i = 0; i < s - 1; i++)
{
f[i + 1] = INF;
}
left = -1;
for (int i = s - 1; i < n; i++)
{
D(printf("f[i]=%d\n", f[i]));
D(printf("%d\n", i));
D(printf("	in:%d\n", i-s));
multi_set.insert(f[i - s + 1]);
while (left < g[i] - 1 && left <= i - s)
{
D(printf("	out:%d\n", left));
multi_set.erase(multi_set.lower_bound(f[left + 1]));
left++;
}
if (multi_set.empty())
{
f[i + 1] = INF;
continue;
}
f[i + 1] = *multi_set.begin() + 1;
}
if (f[n] >= INF)
{
return -1;
}
return f[n];
}

int main()
{
input();
printf("%d\n", work());
return 0;
}