487B


  Posted on 28 Nov 2014
dynamic programming two pointers monotonic queue

Description


Given a sequence of numbers of length . () 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 , and the length of each substrip must be greater than . Output the minimal number of strip it could be divided into.

Tutorial


Use dynamic programming to solve the problem. Let denote the minimal number of pieces that the first numbers can be split into. denote the least possible left boarder of substrip whose right border is which satisfies the condition. Then , where .

One possible way to calculate is to use monotonic queue which can be done in . 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 , which is slower than the push and pop of monotonic queue which is . Quest any element in multiset (e.g. maximum, minimum) in . (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 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 , 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;
}