当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6642:Three Investigators

题目描述
Chitanda owns a sequence $a_1,a_2,\dots,a_n$ with $n$ integers, and she wants to play a game with Skywalkert.

First, Chitanda will select a parameter $k$ and remove $a_{k+1},a_{k+2},\dots,a_n$. Thus there will be exactly $k$ integers in sequence $a$.

Then Skywalkert can select a subsequence of $a$ and remove it from $a$. Assume the selected subsequence is $a_{p_1},a_{p_2},\dots,a_{p_m}$, he should ensure $p_1<p_2<\dots<p_m$ and $a_{p_1}\leq a_{p_2}\leq\dots\leq a_{p_m}$.

Skywalkert can do the above operation for no more than $5$ times. His score is the sum of all the integers selected by him in these no more than $5$ operations.

Given the parameter $k$ selected by Chitanda, write a program to help Skywalkert maximize his score.
输入解释
The first line of the input contains an integer $T(1\leq T\leq 10000)$, denoting the number of test cases.

In each test case, there is one integer $n(1\leq n\leq 100000)$ in the first line, denoting the length of $a$.

In the second line, there are $n$ integers $a_1,a_2,...,a_n(1\leq a_i\leq 10^9)$, denoting the sequence.

It is guaranteed that $\sum n\leq 500000$.
输出解释
For each test case, print a single line containing $n$ integers $s_1,s_2,\dots,s_n$ , where $s_i$ denotes the maximum score of Skywalkert when $k=i$.
输入样例
1
8
8 7 6 5 1 3 2 4
输出样例
8 15 21 26 27 30 30 34
来自杭电HDUOJ的附加信息
Recommend liuyiding

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6642

最后修改于 2020-10-25T23:33:05+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
5000/5000MS(Java/Others) 524288/524288K(Java/Others)