Codeforces 833B The Bakery（主席树 + 决策单调性优化DP）

题目链接 The Bakery

题目大意：目标是把$n$个数分成$k$组，每个组的值为这个组内不同的数的个数，求$k$个组的值的和的最大值。

题目分析：

这道题我的解法可能和大众解法不太一样……我用主席树求$ask(l, r)$——$l$到$r$之间有多少个不同的数。

然后就是$DP$了。

这道题的数据规模是

$n <= 35000$， $k <= 50$

首先直接$DP$的做法还是比较简单的。代码如下。

其中$f[i][j]$为前$i$个数分成$j$组可以得到的最大的和

        rep(i, 1, n){

		　　　　tmp.set(a[i]);

		　　　　f[i][1] = tmp.count();

	　　}

	　　rep(j, 2, k){

		　　rep(i, j, n){

			　　rep(k, 0, i - 1){

				f[i][j] = max(f[i][j], f[k][j - 1] + ask(k + 1, i));

			}

		}

	}

我们发现这样的时间复杂度是$O(n^{2}klogn)$的，效率不够高。

怎么优化呢？

这道题有一个结论：

假设$f[i][j]$的最优方案是从$f[x][j - 1]$得到的，$f[i +1][j]$的最优方案是从$f[y][j - 1]$得到的。

那么一定有 $x <= y$

（证明是某个外国小哥给出的）

我们可以用分治进行优化（也就是整体二分吧）

求$f[i][k]$ $(l <= i <= r)$的时候，我们先求$f[mid][k]$

其中$mid = (l + r) / 2$

求$f[mid][k]$的时候，我们对于$f[j][k - 1]$，$j$从$1$枚举到$mid$

这个时候我们要记录一个$x$，即$f[mid][k]$的最优方案是从$f[x][k - 1]$得到的。

那么我们就可以两边继续递归下去，分别求两个四等分点位置

$f[p1][k]$ $(l <= i <= mid - 1)$ （此时对于$f[j][k - 1]$，$j$从$1$枚举到$x$）

和

$f[p2][k]$ $(mid + 1 <= i <= r)$（此时对于$f[j][k - 1]$，$j$从$x$枚举到$n$）

以此类推

于是上述代码中的时间复杂度中的一个$n$变成了$logn$

时间复杂度 $O(nlog^{2}(n)k)$

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

typedef long long LL;

const int N = 35010;

const int M = 4e6 + 10;

int n, tot, q, a[N];

int T[M], lson[M], rson[M], val[M];

int nxt[N], b[N];

int k;

int f[N][53];

bitset <N> tmp;

int build(int l, int r){

	int rt = tot++;

	val[rt] = 0;

	int m = (l + r) >> 1;

	if(l != r){

		lson[rt] = build(l, m);

		rson[rt] = build(m + 1, r);

	}

	return rt;

}

int update(int rt, int pos, int v){

	int newrt = tot++, tmp = newrt;

	int l = 1, r = n;

	val[newrt] = val[rt] + v;

	while(l < r)

	{

		int m = (l + r) >> 1;

		if(pos <= m)

		{

			lson[newrt] = tot++;

			rson[newrt] = rson[rt];

			newrt = lson[newrt];

			rt = lson[rt];

			r = m;

		}

		else

		{

			rson[newrt] = tot++;

			lson[newrt] = lson[rt];

			newrt = rson[newrt];

			rt = rson[rt];

			l = m + 1;

		}

		val[newrt] = val[rt] + v;

	}

	return tmp;

}

int query(int rt, int pos){

	int ret = 0;

	int l = 1, r = n;

	while(pos > l){

		int m = (l + r) >> 1;

		if(pos <= m){

			ret += val[rson[rt]];

			rt = lson[rt];

			r = m;

		}

		else{

			l = m + 1;

			rt = rson[rt];

		}

	}

	return ret + val[rt];

}

int ask(int l, int r){ return query(T[r], l); }

void init(){

	tot = 0;

	memset(nxt, -1, sizeof(nxt));

	rep(i, 1, n) b[i - 1] = a[i];

	sort(b, b + n);

	int cnt = unique(b, b + n) - b;

	T[0] = build(1, n);

	rep(i, 1, n){

		int id = lower_bound(b, b + cnt, a[i]) - b;

		if(nxt[id] == -1)

			T[i] = update(T[i - 1], i, 1);

		else{

			int t = update(T[i - 1], nxt[id], -1);

			T[i] = update(t, i, 1);

		}

		nxt[id] = i;

	}

}

void solve(int j, int l, int r, int st, int ed){

	if (l > r) return;

	int mid = (l + r) >> 1;

	int x;

	rep(i, st, min(mid, ed)){

		if (f[i - 1][j - 1] + ask(i, mid) >= f[mid][j]){

			f[mid][j] = f[i - 1][j - 1] + ask(i, mid);

			x = i;

		}

	}

	if (l != r){

		solve(j, l, mid - 1, st, x);

		solve(j, mid + 1, r, x, ed);

	}

}

int main(){

	scanf("%d%d", &n, &k);

	rep(i, 1, n) scanf("%d", a + i);

	init();

	rep(i, 1, n){

		tmp.set(a[i]);

		f[i][1] = tmp.count();

	}

/*

	rep(j, 2, k){

		rep(i, j, n){

			rep(k, 0, i - 1){

				f[i][j] = max(f[i][j], f[k][j - 1] + ask(k + 1, i));

			}

		}

	}

*/

	rep(j, 2, k)  solve(j, 1, n, 1, n);

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

	return 0;

}

巴特西

Codeforces 833B The Bakery（主席树 + 决策单调性优化DP）

最新文章

热门文章