HDU 1087 Super Jumping! Jumping! Jumping!

http://acm.hdu.edu.cn/showproblem.php?pid=1087

题意：求递增段最大和
状态转移方程：dp[j] = max(dp[j], dp[i]+v[j])【前提v[j]>v[i], 构成递增】
其中j>i, dp[i]是前i个中的最优状态, v[j]是j的价值

#include <iostream>
using namespace std;

int dp[1005], value[1005];

int main()
{
	int n, i, j, maxs;
	while (cin >> n, n)
	{
		for (i = 0; i < n; i++)
			cin >> value[i], dp[i] = value[i];    //初始化
		maxs = value[0];
		for (i = 0; i < n - 1; i++)
			for (j = i + 1; j < n; j++)
				if (value[j] > value[i])
					dp[j] = max (dp[j], dp[i] + value[j]), maxs = max (maxs, dp[j]);
		cout << maxs << endl;
	}
	return 0;
}

评论

2 楼 基德KID.1412 2011-06-06  

chriszeng87 写道

想问下，dp[j] = max(dp[j], dp[i] + value[j]) 这句并不能保证 i 是当前递增的数组的最后一个吧?

代码中dp[i]是用来更新dp[j]的
for (i = 0; i < n - 1; i++)  
    for (j = i + 1; j < n; j++)

1 楼 chriszeng87 2011-06-06  

想问下，dp[j] = max(dp[j], dp[i] + value[j]) 这句并不能保证 i 是当前递增的数组的最后一个吧?