P5504 [JSOI2011]柠檬

决策单调性优化2

我爱

f_j=max{f_{i-1}+col(i)*(s_{j}-s_{i}+1)^2}

而且 $col_i==col_j$ ,这个是满足的才行

观察后面函数导函数是单调递增的,而要最大化,由上一篇博客可知要决策单调性优化单调栈形式了....

具体怎么说呢?

不难发现,正是因为我们要最大化,对于一个颜色j,越靠前后面那个转移的值越大!

也就是说对于一个决策点 $j<k$ ,j当前不是最优的,j可能会在某个时间点之后成为了最优点

也就是说我们一个单调栈内决策点的最优时间是递减的.....而最优时间可以反映到颜色数上,因为相当于颜色数越多我们最优时间越靠后

辣么我们就可以想出一些方法去维护这个单调栈了....

如果栈顶的两个元素的最优时间早于新决策点i和栈顶的最优时间我们就弹出栈顶

显然i是最优的,但是栈顶的最优时间还在i之前,所以说明他无论如何都不会成为最优时间了,所以我们可以弹出栈顶....

如果栈顶的两个元素的最优时间小于 $s[i]$ 即i颜色数就弹出栈顶

也就是说他已经不再能成为那个决策点了,也就是最优时间已经过了...

做完这两个操作我们再去更新i即可

而怎么求出两个决策点的最优时间比较呢?

可以二分,因为两个决策点一定是某段时间之前一个更优,之后另一个更优,直接二分那个颜色数然后类似的转移一下就好了

所以最后整个算法流程也就是这样了

code:


#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
#define ll long long
int n, a[MAXN], s[MAXN], vis[MAXN];
vector<int> st[MAXN], rc[MAXN];
ll f[MAXN];

inline ll calc(int x, int y) {
	// if(x == y)return f[y] + a[x];
	return f[x - 1] + 1ll * y * y * a[x];
}

inline int bound(int x, int y) {//在x,y中update
	int l = 1, r = n, mid, ret = n + 1;
	// printf("%d %d?%d %d\n", l, r, x, y);
	while(l <= r) {
		mid = (l + r) >> 1;
		// printf("in->%lld %lld?\n", calc(x, mid - s[x] + 1), calc(y, mid - s[y] + 1));
		if(calc(x, mid - s[x] + 1) >= calc(y, mid - s[y] + 1)) {
			ret = mid;
			r = mid - 1; 
		} else l = mid + 1;
	}
	// printf("!!!%d\n", ret);
	return ret;
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		vis[a[i]]++;
		s[i] = vis[a[i]];
	}
	//直接用st维护
	for(int i = 1; i <= n; ++i) {
		int t = a[i];
		// printf("%d?\n", st[t].size());
		while(st[t].size() >= 2 &&
				bound(st[t][st[t].size() - 2], st[t][st[t].size() - 1])
				<= bound(st[t][st[t].size() - 1], i)) {
			// printf("%d %d?\n", bound(st[t][st[t].size() - 2], st[t][st[t].size() - 1]), bound(st[t][st[t].size() - 1], i));
			st[t].pop_back();//只要结尾一段的决策点i最优就一直...
		} st[t].push_back(i);
		// printf("st:%d st2:%d low:%d \n", st[t][st[t].size() - 1], st[t][st[t].size() - 2], bound(st[t][st[t].size() - 1], i));
		while(st[t].size() >= 2 &&
				bound(st[t][st[t].size() - 2], st[t][st[t].size() - 1]) <= s[i]) {
			// printf("%d\n", st[t][st[t].size() - 1]);
			st[t].pop_back();
		}
		// printf("i:%d best choic: %d!\n", i, st[t][st[t].size() - 1]);
		f[i] = calc(st[t][st[t].size() - 1], s[i] - s[st[t][st[t].size() - 1]] + 1);
		// printf("finial:%lld\n", f[i]);
	}
	printf("%lld\n", f[n]);
	return 0;
}

还有noi.ac的一道抄袭这个题的决策单调性优化

有一个至关重要的细节就是如果我们的二分二分不出时间

说明前面的决策点永远都不可能成为最优决策点了....

那么这个时候我们只需要压住栈即可,因为珍贵的栈顶是最优的

即bound函数返回n+1

code:


#include<bits/stdc++.h>
using namespace std;
#define ll long double
const int MAXN = 1e6 + 7;

int n, k;
int a[MAXN], vis[MAXN], s[MAXN];
vector<int> st[MAXN];
ll f[MAXN], qwq[MAXN];

inline ll calc(int x, int y) {
	return f[x - 1] + qwq[y];
}

inline int bound(int x, int y) {
	int l = 1, r = n, ret = n + 1, mid;
	// printf("in->%d %d?\n", x, y);
	while(l <= r) {
		mid = (l + r) >> 1;
		if(calc(x, mid - s[x] + 1) >= calc(y, mid - s[y] + 1)) {
			// printf("this mid is ok%d\n", mid);
			ret = mid;
			r = mid - 1;//这个决策点x更优,再靠前
		} else l = mid + 1;
	}
	// printf("end with %d\n", ret);
	return ret;
}

inline void init() {
	if(k == 2) {
		for(int i = 1; i <= n; ++i) {
			qwq[i] = 1ll * i;
		}
	} else if(k == 3)
		for(int i = 1; i <= n; ++i) {
			qwq[i] = pow(i, 1.5);
			// printf("%d %Lf\n", i, qwq[i]);
		} else if(k == 4)
		for(int i = 1; i <= n; ++i) {
			qwq[i] = 1ll * i * i;
		}
}

int main() {
	scanf("%d%d", &k, &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		vis[a[i]]++;
		s[i] = vis[a[i]];
	}
	init();
	for(int i = 1; i <= n; ++i) {
		int t = a[i];
		// puts("Ha1");
		while(st[t].size() >= 2 &&
				bound(st[t][st[t].size() - 2], st[t][st[t].size() - 1]) <= bound(st[t][st[t].size() - 1], i)) {
			// printf("out..->%d?%d?\n", st[t][st[t].size() - 1], st[t][st[t].size() - 2]);
			st[t].pop_back();
		}
		// puts("Ha2");
		st[t].push_back(i);
		while(st[t].size() >= 2 &&
				bound(st[t][st[t].size() - 2], st[t][st[t].size() - 1]) <= s[i]) {
			// puts("qwq");
			st[t].pop_back();
		}
		// printf("wei shen me?%d %d?\n", i, st[t][st[t].size() - 1]);
		f[i] = calc(st[t][st[t].size() - 1], s[i] - s[st[t][st[t].size() - 1]] + 1);
		// printf("finish:%Lf\n", f[i]);
	}
	printf("%.6Lf\n", f[n]);
	return 0;
}

夏晓光(loveJY)的博客

P1912 [NOI2009]诗人小G