HDU - 1087 Super Jumping! Jumping! Jumping! 解题报告
题目大意：
给你一串数（1000个），问你他的各个上升子序列（可以不连续）的所有元素和中最大的是多少
dp建立：
设v[i]为第i个数的值，a[i]为以第i个数结尾（这个数被选上）的上升子序列所有元素和的最大值
递推关系：a[i]=max{a[j-1]+v[i]} (v[j-1]<v[i]&&1<j<=i)
给你一串数（1000个），问你他的各个上升子序列（可以不连续）的所有元素和中最大的是多少
dp建立：
设v[i]为第i个数的值，a[i]为以第i个数结尾（这个数被选上）的上升子序列所有元素和的最大值
递推关系：a[i]=max{a[j-1]+v[i]} (v[j-1]<v[i]&&1<j<=i)
边界条件：a[i]=v[i]
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#define N 1050
using namespace std;
long long int a[N]={0};
long long int v[N]={0};
int n;
void input()
{
for(int i=1;i<=n;i++)
{
scanf("%lld",&v[i]);
}
}
void dp()
{
memset(a,0,sizeof(a));
a[1]=v[1];
for(int i=2;i<=n;i++)
{
a[i]=v[i];
for(int j=2;j<=i;j++)
{
if(v[j-1]>=v[i])continue;
if(a[i]<a[j-1]+v[i])a[i]=a[j-1]+v[i];
}
}
}
long long int find()
{
long long int maxx=-10000000;
for(int i=1;i<=n;i++)
{
if(maxx<a[i])maxx=a[i];
}
return maxx;
}
int main()
{
while(1)
{
cin>>n;
if(n==0)break;
input();
dp();
cout<<find()<<endl;
}
}
Momenta公司福利 534人发布