题解 P5504 【[JSOI2011]柠檬】

这里说一种决策单调性+单调栈+二分的做法。 首先考虑是否有决策单调性。对于一个$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 ```cpp #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\}$彼此之间线性无关。