1650 - 前缀最小值-东方博宜OJ

题目描述

求一个数列的所有前缀最小值之和。

即：给出长度为 $n$ 的数列 $a_i$ ,求出对于所有 $1\leqi\leqn$ ， $min(a_1,a_2,...,a_i)$ 的和。

比如，有数列： $666$ $304$ $692$ $188$ $596$ ，前缀最小值为： $666$ $304$ $304$ $188$ $188$ ，和为 $1650$ 。

对于每个位置的前缀最小值解释如下：对于第 $1$ 个数 $666$ ，只有一个数，一定最小；对于第 $2$ 个数，求出前两个数的最小数，是 $304$ ；对于第 $3$ 个数，求出前 $3$ 个数的最小数是 $304 \dots$ 其余位置依次类推，最后求前缀最小值的和。

由于读入较大，数列由随机种子生成。

其中 $a[1]=x$ ， $a[i]=(379 \times a[i-1]+131) \mod 997$ 。（ $mod$ 代表求余数）

输入

一行两个正整数 $n$ , $x$ ，分别表示数列的长度和随机种子。( $n \leq 100000$ , $x < 997$ )

输出

一行一个正整数表示该数列的前缀最小值之和。

样例

5 666

说明

【样例解释】

数列为 $666,304,692,188,596$ ，前缀最小值为 $666,304,304,188,188$ ，和为 $1650$ 。

来源

动态规划

标签

题目参数

上一题下一题