题目链接:http://poj.org/problem?id=2533
dp[now]表示从头到当前位置 最长的递增子序列长度。
有两张决策,即含不含当前位置。
dp[now]=max(dp[last]+1,dp[now]) last<now且p[last]<p[now]
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=1010; 6 int dp[maxn]; 7 int p[maxn]; 8 int n; 9 10 int main() 11 { 12 while(scanf("%d",&n)!=EOF) 13 { 14 int ans=0; 15 memset(dp,0,sizeof(dp)); 16 p[0]=-1; 17 for(int i=1;i<=n;i++) 18 { 19 scanf("%d",&p[i]); 20 for(int j=0;j<i;j++) 21 if(p[j]<p[i]) 22 { 23 dp[i]=max(dp[j]+1,dp[i]); 24 ans=max(ans,dp[i]); 25 } 26 } 27 printf("%d ",ans); 28 } 29 }