NYOJ 79 拦截导弹 （经典dp） 单调递增最长子序列
#include<stdio.h> #include<stdlib.h> int main() { int n,m,i,j,max; int a[20],dp[20]; scanf("%d",&n); while(n--) { scanf("%d",&m); for(i=0;i<=m-1;i++) { scanf("%d",&a[i]); dp[i]=1; //dp[i]的最小值为1 } for(i=m-2;i>=0;i--) { for(j=i+1;j<=m-1;j++) { if((a[j]<a[i])&&(dp[i]<dp[j]+1)) //最长递减子序列则a[j]<a[i],而最长递增子序列则a[j]>a[i]。。。。好好体会。。。。 { dp[i]=dp[j]+1; //更新dp[i] } } } max=dp[0]; for(i=0;i<=m-1;i++) { if(max<dp[i]) max=dp[i]; } printf("%d\n",max); } system("pause"); return 0; }