2958. 求上升子序列和的最大值

单点时限: 2.0 sec

内存限制: 256 MB

由非负整数 满足 时被称为长度为 的上升序列。

一个长度为 的序列 ,存在多种上升子序列:

例如:序列 1, 7, 3, 5, 9, 4, 8 的上升子序列有 (1, 7)、(3, 5, 8)、(1, 3, 5, 9) 等。这些上升子序列中序列和最大为 18,为上升子序列 1, 3, 5, 9 的和。

对于给定的序列,求出上升子序列和的最大值。

输入格式

第 1 行:整数 () 为问题数

第 2 行:第 1 个问题的整数

第 3 行:n 个整数, 由一个空格隔开。这些数的值有些可能是相等的。

后面是第 2 ∽ T 个问题的数据。格式与第 1 个问题相同。

输出格式

对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0: 等),然后在一行中输出上升子序列和的最大值。

样例

Input
2
7
1 7 3 5 9 4 8
4
100 20 20 3
Output
case #0:
18
case #1:
100

403 人解决,466 人已尝试。

541 份提交通过,共有 1140 份提交。

1.5 EMB 奖励。

创建: 7 年,9 月前.

修改: 1 年,4 月前.

最后提交: 2 天,11 小时前.

来源: 2012年程序设计实践第8次上机考试

题目标签
DP