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; }