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;} 1 楼 chriszeng87 2011-06-06 想问下，dp[j] = max(dp[j], dp[i] + value[j]) 这句并不能保证 i 是当前递增的数组的最后一个吧? 2 楼 基德KID.1412 2011-06-06 chriszeng87 写道想问下，dp[j] = max(dp[j], dp[i] + value[j]) 这句并不能保证 i 是当前递增的数组的最后一个吧?