Gay Life之图包
$sequence.cpp;;;time;limit:1s;;;memory;limit:256MB$
Description
$;;;;;;$$Peter;Shao$有$n$个图包(压缩包形式),每个图包内有$a_i$张$AKUF$的照片.(图包名称按字典序排序,排序后从$1$开始编号).
$;;;;;;$现在可以将图包扔进若干个文件夹,每个文件夹内的图包的编号必须是连续的(这样方便$Peter;Shao$一次性拖进文件夹中,省下时间撩妹).
$;;;;;;$定义第$i$个文件夹对$Peter;Shao$的吸引程度$x_i$为这个文件夹中所有图包含$AKUF$照片的最大值(显然第$0$个文件夹中没有$AKUF$的照片).
$;;;;;;$显然$Peter;Shao$不会满足于含$AKUF$照片最多的文件夹,他的图包中还有一些妹子的照片.由于$Peter;Shao$是个资深老司机+巨神,所以他一个文件夹中三次元妹子的不可看程度为$sum_{i=1}^{m}|x_i-x_{i-1}|$,二次元妹子的不可看程度为$sum_{i=1}^{m}(x_i-x_{i-1})^2$,其中$m$为文件夹总数.现在为了$Peter;Shao$观赏愉悦,要求文件夹中三次元妹子的不可看程度的最小值以及划分方案数,二次元妹子的不可看程度的最小值以及划分方案数.
Input
第一行一个整数$n$.第二行$n$个正整数$a_1,...,a_n$.
按顺序输出四个非负整数表示答案,其中两个方案数均对$10^9+7$取模.
Sample Input4
10 30 20 30
Sample Output
30
6
500
3
HINT
$n;leq;10^5,1;leq;a_i;leq;10^9$.
P.S."欲问$Peter;Shao$和$AKUF$是谁,请看图."
"对题目名称有歧义?!"
Solution
- 题意
给定一个长度为$n$的正整数序列$a$。可以将序列分成若干段，定义第$i$段的权值$x_i$为这一段中所有数的最大值，特殊地，$x_0=0$。求$sum_{i=1}^{m}|x_i-x_{i-1}|$的最小值以及划分方案数，$sum_{i=1}^{m}(x_i-x_{i-1})^2$ 的最小值以及划分方案数，其中$m$为划分的段数。
- 口胡题解
从后往前单调栈维护一个不上升序列，记为序列$s$。
记$s$的长度为$l$，$s[l+1]=0$。将$s$在$a$的位置记为$d$。
显然，对于一个序列$a$，$sum_{i=1}^{m}|x_i-x_{i-1}|$的最小值为序列中最大的数。
在$s_i$与$s_{i+1}$之间，定一个断点有$(d_i-d_{i+1})$种方案，不定断点，有$1$种方案。
所以总方案数为$prod_{i=1}^{m-1}(d_{i}-d_{i+1}+1)$。
易证$sum_{i=1}^{m}(x_{i}-x_{i-1})^2$的最小值为$sum_{i=1}^{l}(s_{i}-s_{i+1})^2$。
显然，s中的每一种值至少需要出现一次，所以对于每种值的情况进行考虑。
在$[d_{i-1},d_i)$这段区间内定一个断点，有$(d_i-d_{i-1})$种方案，不定断点，有$1$种方案。
由于每个值都必须出现一次，所以不能出现都不定断点的情况。
记所有不同的值为$b$，则总方案数为$prod_{i=1}^{|b|}(prod_{s[j]=b[i]}(d_{j-1}-d_{j}+1)-1)$