自动搬运

查看原文

来自洛谷，原作者为

	皎月半洒花 在那之前，你要多想。

搬运于2025-08-24 22:11:27，当前版本为作者最后更新于2019-10-29 16:50:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这里说一种决策单调性+单调栈+二分的做法。

首先考虑是否有决策单调性。对于一个$i$，设其最优决策点为$o_i$，那么一定有$color[i]=color[o_i]$。

那么转移方程就很容易列出来：

$$f_i=\max_{color_i=color_j}\{ f_{j-1}+color_i\cdot (sum_i-sum_j+1)^2\} \quad (j<i) $$

观察这个式子，会发现一个性质，因为转移只在相同颜色间转移，所以对于后面的$color_i\cdot (sum_i-sum_j+1)$是随着$i$的变化而单增的，也就是说对于一个$j_1<j_2$，一开始时满足$j_1$更优，那么随着$i$增大$j_2$就永远不会比$j_1$更优，因为二次函数的增长对于更优的$j_1$只会增长得更快（类似于输在起跑线上233）。

所以发现是具有决策单调性的，即同一段区间的、同一种颜色的决策点会出现不增的局面。

那么一个自然的想法使用单调栈维护，发现第二个元素比第一个元素优的时候$pop$掉即可。但是问题在于当前点的最终决策点可能会更靠前，比如$j_1<j_2<j_3$但$val(j_1)>val(j_3)>val(j_2)$，就应该从$j_1$转移。

但事实上，根据大趋势而言，出现上述那种情况当且仅当一段时间内$j_2$比$j_1$更优（否则当时就不会入栈），之后$j_1$开始比$j_2$优（导致出现了现在的$val(j_1)>val(j_2)$）。所以我们可以二分出一个确定的时间（此处时间的流淌用新的$color_i$个数的增多刻画）优劣关系发生变化，而如果这个时间在$\leq sum_i$ 之前，那么就要$pop$掉$j_2$，因为没用了。

所以，每次加入元素的时候都要判断当前栈中$top-1$超过$top$ 的元素的时间是否小于等于$top$超过要添加进来的$x$的时间，如果是就要把$top$给$pop$掉，因为在$top$超过$x$之前$top$就死了。

…… 这么一比较似乎斜率优化简直是pj算法，比决策单调性的思维难度不知道低到哪里去了（雾）。然而事实上这是比较hard的决策单调性，比较普通的满足全局的决策点单调，但是这道题要分颜色考虑才能发现决策点单调233

#define o(a, b) stk[a][b]
#define sz(k) stk[k].size()
#define sp(k) stk[k].size() - 1
#define sq(k) stk[k].size() - 2
il LL calc(int p, int t){
    return dp[p - 1] + 1ll * base[p] * t * t ;
}
il int chk(int x, int y){
	rg int ret = N + 1 ;
	rg int l = 1, r = N, mid ; 
	while (l <= r){
		mid = (l + r) >> 1 ; 
		if (calc(x, mid - s[x] + 1) >= calc(y, mid - s[y] + 1))
			ret = mid, r = mid - 1 ; else l = mid + 1 ; 
	}
	return ret ;
}
int main(){
	cin >> N ; int i ; 
	for (i = 1 ; i <= N ; ++ i) 
		scanf("%d", &base[i]), s[i] = ++ buc[base[i]] ; 
	for (i = 1 ; i <= N ; ++ i){
		rg int t = base[i] ; 
		while (sz(t) >= 2 && chk(o(t, sq(t)), o(t, sp(t))) <= chk(o(t, sp(t)), i)) 
			stk[t].pop_back() ; stk[t].push_back(i) ; 
		while (sz(t) >= 2 && chk(o(t, sq(t)), o(t, sp(t))) <= s[i]) stk[t].pop_back() ;
		dp[i] = calc(o(t, sp(t)), s[i] - s[o(t, sp(t))] + 1) ;  
	}
	cout << dp[N] << endl ; return 0 ;
}

$\rm By~the~way$，一般情况下决策单调性只要写好分治就可以了，分治可以用的前提是当前维度的$\{f_i\}$彼此之间线性无关。