题意
给定长为\(n\)的序列\(\{a_i\}\),分成恰好\(k\)个非空连续段使得这\(k\)的极差之和最小,对\(k=1,2,\cdots,n\)分别求解。\(n\le 5000\)
做法
定义:令\(f_{i,j}\)为将前\(i\)个数分成\(j\)段的最小极差之和,令\(w_{l,r}\)为\(a_l,\cdots,a_r\)的极差。
按\(j=1\sim n\)按层转移:
\[f_{i,j}=\min_{i_1=1}^{i}f_{i_1-1,j-1}+w_{i_1,i} \]观察:对任意\(i_1<i_2\le i\),若\(f_{i_1-1,j-1}+w_{i_1,i}\le f_{i_2-1,j-1}+w_{i_2,i}\),则对任意\(i'>i\),\(f_{i_1-1,j-1}+w_{i_1,i'}\le f_{i_2-1,j-1}+w_{i_2,i'}\)。即对于\(i_1<i_2\),\(i_1\)对某一段后缀的转移比\(i_2\)优。
做法一\(O(n^2\log n)\):
考虑对于\(i=j\sim n\),动态维护一个决策序列\(j\le i_1,i_2,\cdots,i_{len}\le i\)(其中的每个点可能会成为某个\(i'\ge i\)的最优决策点),满足\(f_{i_k-1}+w_{i_k,i}>f_{i_{k+1}-1}+w_{i_{k+1},i}\)。\(i_{len}\)为\(i\)的最优决策点。
对应相邻的\(i_k,i_{k+1}\),可以二分出\(i_{k+1}\)何时会再比\(i_k\)更优,此时可以将其踢出序列。
序列用链表维护。实测与\(\text{std}\)跑得差不多快。
做法二(官方题解)\(O(n^2\alpha(n))\):
考虑对于\(i=j\sim n\),动态维护一个决策序列\(j\le i_1,i_2,\cdots,i_{len}\le i\)(其中的每个点可能会成为某个\(i'\ge i\)的最优决策点),满足\(f_{i_k-1}+w_{i_k,i}>f_{i_{k+1}-1}+w_{i_{k+1},i}\)。\(i_{len}\)为\(i\)的最优决策点。
考虑从\(i\)到\(i+1\)不同\(k\)的\(w\)增量\(\Delta_k=w_{k,i+1}-w_{k,i}\)。
增量的形式可以表示为\((l_1,r_1,\delta_1)(l_2,r_2,\delta_2)\cdots(l_{tot},r_{tot},\delta_{tot})\)(\(r_i=l_{x+1}-1\)、\(\delta_x<\delta_{x+1}\)),满足\(\forall k\in [l_x,r_x].\Delta_k=\delta_x\)
可以如此考虑维护决策序列:
从\(x=tot\sim 1\),找到\([l_x,r_x]\)中最大的决策点\(i_k\)(或者说,找到\(\le r_k\)的最大决策点),反复与其后面一个决策点进行比较,如果更优则将后面一个决策点踢掉。
观察2:可以不按\(x\)降序的顺序而是任意对于\(\{1,2,\cdots,tot\}\)的任意顺序,进行踢决策点的操作。
观察3:对于所有可能的\(r_x\),可以通过两个单调栈,分别维护后缀最小值和后缀最大值的过程得到。
对于某个位置\(pos\),如何找到\(\le pos\)的最大决策点和\(> pos\)的最小决策点,可以通过并查集得到。
标签:Great,le,Wall,多校,tot,决策,cdots,len,序列 From: https://www.cnblogs.com/Grice/p/18338566