1544: 阿正的子母序列
题目描述
最近阿正刚学习完字符串,对解决子串和母串的问题乐此不疲,但希望阿正进步的学长又给阿正出了一道序列和子序列的难题,你能帮帮阿正吗?
给定一个长度为N序列A,对A的子序列B有如下定义:
(1) B由A中的K个元素组成;(1<=K<=N)
(2) B中所有元素按在a中的出现顺序进行排列;
如1 2 4 5 3 的子序列可以是 1 2 4 和 1 2 3 ,但不能是2 1 4 或者 6 1 4。
而连续子序列则是B中的元素要在A中连续,即1 2 4 5 是A的一个连续子序列,但1 2 4 3虽然是A的子序列,却不是连续子序列。
定义A的两个子序列P、Q相等,当且仅当满足以下条件:
(1) 两个子序列长度相等; (1<=KP=KQ<=N)
(2) 两个子序列中所有对应元素都相等,即对于子序列中所有的元素,都有Pi=Qi(0<=i<k);
(3) 两个子序列首元素在母序列中出现的位置相等;
对于第三个条件,意即在母序列 "1 2 3 1 2 3" 中,首元素出现在0的第一个"1 2 3"与首元素出现在3的第二个"1 2 3" 不相等。
现在学长给阿正了一个长度为N的序列A,不仅要让阿正求出A中不相等的连续非递减子序列的数量,同时,学长将一个序列的权值定义为该序列的长度,要让阿正求出A的所有不相同的连续非递减子序列权值总和。
输入
第一行一个正整数N,代表序列A的长度; (0<N<=10000)
第二行N个整形范围内的整数,依次代表序列A中的各元素。
输出
第一行一个正整数代表A的不同的连续非递减子序列个数。
第二行一个正整数代表A的所有连续非递减子序列权值总和。
样例输入 复制
5
1 2 4 5 3
样例输出 复制
11
21
提示
[1]、[1 2]、[1 2 4]、[1 2 4 5]
[2]、[2 4]、[2 4 5]
[4]、[4 5]
[5]
[3]
共11个;
对上述非递减子序列,权值依次为:
1、2、3、4
1、2、3
1、2
1
1
总和为21。