hdoj 1087 (DP)

时间:2024-08-25 17:05:20

代码:

#include<iostream>  
#include<cmath>  
using namespace std; 
int a[1005], dp[1005]; 
int main() 

    int n,sum,i,j; 
    while( scanf("%d",&n)&&n){ 
           for( i=0; i<n; i++){ 
                scanf("%d",&a[i]); 
                dp[i]=a[i]; 
           } 
           sum=0; 
           for( i=1; i<n; i++){ 
                for( j=0; j<i; j++){ 
                     if( a[i]>a[j]) 
                         dp[i]=max(dp[i],dp[j]+a[i]); 
                } 
                if( dp[i]>sum) 
                    sum=dp[i]; 
           }  
           printf("%d\n",sum);          
    } 
    return 0; 
}