_皎月半洒花 的博客

_皎月半洒花 的博客

反抗命运的镇魂曲停歇之前,你绝对不可以说我懦弱,绝对不可以说我没有殊死一搏。

题解 P5504 【[JSOI2011]柠檬】

posted on 2019-10-29 16:50:32 | under 题解 |

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

首先考虑是否有决策单调性。对于一个 $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\}$ 彼此之间线性无关。