【算法系列学习】[kuangbin带你飞]专题十二 基础DP1 E - Super Jumping! Jumping! Jumping!

时间:2022-09-04 02:59:42

https://vjudge.net/contest/68966#problem/E

http://blog.csdn.net/to_be_better/article/details/50563344

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#define INF 0x3f3f3f3f
using namespace std;
int n;
const int maxn=1e3+;
int a[maxn];
int dp[maxn];
int main()
{
while(scanf("%d",&n)==&&n)
{
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=;i<=n;i++)
{
int ans=-INF;
for(int k=;k<i;k++)
{
if(a[i]>a[k])
{
ans=max(ans,dp[k]);
}
}
dp[i]=ans+a[i];
}
int ans=-INF;
for(int i=;i<=n;i++)
{
ans=max(ans,dp[i]);
}
printf("%d\n",ans);
}
return ;
}