HDU1087 跳棋

跳棋"/>

HDU1087 跳棋

题目：.php?pid=1087

输入一串数字，从左到右，从start到end，每次经过一个数字，必须比上一次大，求经过的数字最大和。

思路：

简单DP。DP[i]表示从start跳到第i个时的最大和。dp[i]=max(dp[j]+a[i]),j<i。从前i个找到最大值，再跳到第i个。

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn = 1010;
int main()
{int T,i;int a[maxn],dp[maxn];while (cin >> T&&T != 0){memset(a, 0, sizeof(a));memset(dp, 0, sizeof(dp));for (i = 1; i <= T; i++)cin >> a[i];dp[1] = a[1];for (i = 2; i <= T; i++){dp[i] = a[i];for (int j = 1; j < i; j++){if (a[j] < a[i])dp[i] = max((dp[j] + a[i]), dp[i]);}}int ans = 0;for (i = 1; i <= T; i++){ans = max(ans, dp[i]);}cout << ans << endl;}return 0;
}