HDU 1807 Super Jumping! Jumping! Jumping!

一个最大上升子序列问题

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

[cpp] 
<span style="font-size:18px;color:#000099;"><strong>#include<stdio.h> 
__int64 dp[1010],maxn,t; 
int a[1010]; 
int main() 
{ 
    int n,i,j; 
    while(scanf("%d",&n)&&n) 
    { 
       for(i=0;i<n;i++) 
         scanf("%d",&a[i]); 
       dp[0]=a[0];t=0; 
       for(i=1;i<n;i++) 
       { 
           maxn=0; 
          for(j=0;j<i;j++) 
           if(a[j]<a[i]&&dp[j]>maxn) maxn=dp[j]; 
          dp[i]=a[i]+maxn; 
          t=t>dp[i]?t:dp[i]; 
       } 
       printf("%I64d\n",t); 
    } 
    return 0; 
} 
</strong></span> 

补充：软件开发 , C++ ,

上一个：B+树（C++实现）
下一个：SPOJ 1043 Can you answer these queries I（GSS1 线段树）