题目

由非负整数 $b_i(0⩽i<m−1) $满足 $(i<j,b_i<b_j）$时被称为长度为 $m $ 的上升序列。

一个长度为 $n$ 的序列 $a_0,a_1,\dots ,a_{n-1}$，存在多种上升子序列：

$a_{i_0},a{i}_1,\dots ,a{i}_k(0⩽i_0<i_1<\dots <i_k<n)$。

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

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

输入格式

第 1 行：整数 T (1≤T≤10) 为问题数

第 2 行：第 1 个问题的整数 n（1⩽n⩽5000）

第 3 行：n 个整数a（0⩽ai⩽4000）, 由一个空格隔开。这些数的值有些可能是相等的。

后面是第 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

解题思路

dfs/dp都可以，使用图来解释更加直观：

用dp来解释的话就是对于状态转移方程来说，每往下走一个的时候遍历所有前面的结果来判断哪一个加上来以后结果是最大的就取哪个

$sum[i]=min(sum[n{]}_{n=0}^{n-1})+a[i]$

int main(int argc, const char * argv[])
{
	int C;
	cin >> C;
	for (int _ = 0; _ < C; ++_)
	{
		cout << "case #" << _ << ":" << endl;
		int len;
		cin >> len;
		int num[len];
		for (int i = 0; i < len; ++i)
			cin >> num[i];
		// input
		int dp[len];
		dp[0] = num[0];
		for (int i = 1; i < len; ++i)
		{
			vector<int> record;
			for (int j = 0; j < i; ++j)
				if (num[j] < num[i])
					record.emplace_back(dp[j]);
			if (record.empty())
			{
				dp[i] = num[i];
				continue;
			}
			dp[i] = num[i] + *max_element(record.begin(), record.end());
		}
		cout << *max_element(dp, dp + len - 1) << endl;
	}
	return 0;
}