HDU-P1087:Super Jumping! Jumping! Jumping![动态规划]
题目
思路
又是英文题面,不过思路还是很清晰的,题目要求找一条单调递增的序列,使得经过路径的数字和最大,只需要将求解最长递增序列的代码稍作修改即可。
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int solve(int a[], int N)
{
int t[N];//此数组用来标记以当前坐标结束的最大值
for(int i = 0; i < N; ++i)
t[i] = a[i];
for(int i = 1; i < N; ++i) //i从0开始效果是一样的
for(int j = 0; j < i; ++j)
if(a[j]<a[i]&&t[i]<t[j]+a[i]) //状态转移条件
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 < N; ++i)
scanf("%d", &arr[i]);
printf("%d\n", solve(arr,N));
}
return 0;
}