HDOJ 1087
寻找最大的一条递增子序列。
状态转移方程：dp[i]=max(dp[j])+a[i],其中i>j且a[i]>a[j] .
#include<iostream>
#include<cstring>
#define inf 0x3f3f3f
using namespace std;
int n,a[1010],dp[1010],ans;
int max(int a,int b){ return a>b?a:b;}
int main(){while(cin>>n){if(n==0) break;memset(dp,0,sizeof(dp));memset(a,0,sizeof(a));for(int i=1;i<=n;i++){cin>>a[i];}//状态转移方程：dp[i]=max(dp[j])+a[i]//其中i>j且a[i]>a[j] for(int i=1;i<=n;i++){ans=-inf;for(int j=0;j<i;j++){if(a[i]>a[j])ans=max(ans,dp[j]); } dp[i]=ans+a[i];}ans=-inf;for(int i=1;i<=n;i++)ans=max(dp[i],ans);cout<<ans<<endl;}return 0;
}