题解 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

#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 ;
}