一道需要用堆初始化的\(DP\)

原题链接

显然对于每一个部分，当\(b[i]\)为\(a\)对于部分的中位数时，差错最小。设\(S(x,y)\)表示\(x\sim y\)这一部分的差错。

\(DP\)的转移方程应该并不难推。

定义\(f[i][j]\)表示前\(i\)个数字分成\(j\)组导致的差错的最小值。

\(\qquad\qquad f[i][j]=\min\limits_{k=0}^{i-1}\{f[i][j],f[k][j-1]+S(k+1,i)\}\)

如果我们直接暴力计算\(S\)，显然会超时，所以我们需要初始化\(S\)，且因为在初始化过程中需要用到动态中位数，所以我们采用一个小根堆和一个大根堆来维护。

我是维护小根堆堆顶作为中位数。

先在小根堆中插入第一个数，定为当前中位数。

然后循环扫到下一个数，若该数比当前小根堆堆顶小，则插入大根堆，否则插入小根堆。

而在插入过程中，必须保证小根堆的大小比大根堆大\(1\)或相等，而在循环的过程中，小根堆堆顶即是当前区间内的中位数。

#include<cstdio>

#include<queue>

#include<vector>

#include<cstring>

using namespace std;

const int N = 2010;

const int K = 27;

int f[N][K], a[N], v[N][N];

priority_queue<int>bg;

priority_queue<int, vector<int>, greater<int> >sm;

int re()

{

	int x = 0;

	char c = getchar();

	bool p = 0;

	for (; c<'0' || c>'9'; c = getchar())

		p = (c == '-' || p) ? 1 : 0;

	for (; c >= '0'&&c <= '9'; c = getchar())

		x = x * 10 + (c - '0');

	return p ? -x : x;

}

inline int minn(int x, int y)

{

	return x < y ? x : y;

}

int main()

{

	int i, j, n, m, k, s_sm, s_bg;

	while (1)

	{

		n = re();

		m = re();

		if (!n && !m)

			return 0;

		for (i = 1; i <= n; i++)

			a[i] = re();

		for (i = 1; i <= n; i++)

		{

			while (!sm.empty())

				sm.pop();

			while (!bg.empty())

				bg.pop();

			for (j = i + 1, s_sm = a[i], s_bg = 0, sm.push(a[i]); j <= n; j++)

			{

				if (a[j] < sm.top())

				{

					bg.push(a[j]);

					s_bg += a[j];

				}

				else

				{

					sm.push(a[j]);

					s_sm += a[j];

				}

				if (sm.size() > bg.size() + 1)

				{

					bg.push(k = sm.top());

					s_sm -= k;

					s_bg += k;

					sm.pop();

				}

				if (bg.size() > sm.size())

				{

					sm.push(k = bg.top());

					s_bg -= k;

					s_sm += k;

					bg.pop();

				}

				v[i][j] = s_sm - sm.size()*sm.top() + bg.size()*sm.top() - s_bg;

			}

		}

		memset(f, 60, sizeof(f));

		f[0][0] = 0;

		for (j = 1; j <= m; j++)

			for (i = j; i <= n; i++)

				for (k = 0; k < i; k++)

					f[i][j] = minn(f[i][j], f[k][j - 1] + v[k + 1][i]);

		printf("%d\n", f[n][m]);

	}

	return 0;

}