HDU 1807 Super Jumping! Jumping! Jumping!

一个最大上升子序列问题

dp[i] 记录了在i之前且在i位置上的最大上升序列和，dp[i]等于前面a[j]

[cpp]
#include
__int64 dp[1010],maxn,t;
int a[1010];
int main()
{
int n,i,j;
while(scanf("%d",&n)&&n)
{
for(i=0;i scanf("%d",&a[i]);
dp[0]=a[0];t=0;
for(i=1;i {
maxn=0;
for(j=0;j if(a[j]maxn) maxn=dp[j];
dp[i]=a[i]+maxn;
t=t>dp[i] t:dp[i];
}
printf("%I64d\n",t);
}
return 0;
}