1257 hdu

#include<stdio.h> 

 #include<string.h> 

 int a[100010]; 

 int dp[100010]; 

 int main() 

 { 

int i,j,k; 

int n,m; 

int mindp; 

while(scanf("%d",&n)!=EOF) 

{ 

for(i=1;i<=n;i++) 
  

scanf("%d",&a[i]); 

dp[1]=1; 

for(i=2;i<=n;i++) 

{ 

mindp=0; 

for(j=1;j<i;j++) 

{ 

if(a[i]>a[j]&&dp[j]>mindp) 
  

mindp=dp[j]; 

} 

dp[i]=mindp+1; 

} 

k=0; 

for(i=1;i<=n;i++) 

if(k<dp[i]) 

k=dp[i]; 

printf("%d\n",k); 
  

} 

return 0; 
}
状态转移方程
if(a[i]>a[j]&&dp[j]>mindp) 
mindp=dp[j];
}
dp[i]=mindp+1;