HDUP1087:SuperJumping!Jumping!Jumping![动态规划]

HDU-P1087:Super Jumping! Jumping! Jumping![动态规划]

题目

题目链接

思路

又是英文题面，不过思路还是很清晰的，题目要求找一条单调递增的序列，使得经过路径的数字和最大，只需要将求解最长递增序列的代码稍作修改即可。

代码

#include
#include
#include
using namespace std;
int solve(int a[], int N)
{
int t[N];//此数组用来标记以当前坐标结束的最大值
for(int i = 0; i t[i] = a[i];
for(int i = 1; i for(int j = 0; j if(a[j] t[i]=t[j]+a[i];
return *max_element(t,t+N);//北大mooc上了解到的函数
}
int main(void)
{
int N, arr[1005];
while(~scanf("%d", &N) && N) {
for(int i = 0; i scanf("%d", &arr[i]);
printf("%d\n", solve(arr,N));
}
return 0;
}