其实dp之前早就做过了，感觉有点遗忘，拿来复习复习。

1 /* 2 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。 3 但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。 4 某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 5 输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）， 6 计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 7 */ 8 /* 9 分析：10 最多能拦截多少导弹，相当于求最大非上升子序列的长度11 最少要配备多少套这种导弹拦截系统，相当于求最长上升序列的长度12 */13 //dp[i]表示前i个导弹中导弹i最多能拦截到的导弹的个数，则有dp[i]=max(dp[j])+1(其中h[i]<=h[j]&&0<=j
      
       22 #include
       
        23 #include
        
         24 const int inf=1e9;25 using namespace std;26 int h[100];27 int dp1[100];//保留最长非上升子序列28 int dp2[100];//最长递增子序列29 30 int main(){31     int n;32     while(~scanf("%d",&n)){33         for(int i=1;i<=n;i++){34             scanf("%d",&h[i]);35         }36         memset(dp1,0,sizeof(dp1));37         memset(dp2,0,sizeof(dp2));38         int umax=0,dmax=0;39         //求最长非上升子序列40         for(int i=1;i<=n;i++){41             int ans=0;42             for(int j=0;j
         
          ans){45                     ans=dp1[j];46                 }47             }48             dp1[i]=ans+1;//加上自己本身49             dmax=max(dmax,dp1[i]);50         }51         //求最长上升子序列52         for(int i=1;i<=n;i++){53             int ans=0;54             for(int j=0;j
          
           h[j]&&dp2[j]>ans){56                     ans=dp2[j];57                 }58             }59             dp2[i]=ans+1;60             umax=max(dp2[i],umax);61         }62         printf("%d %d\n",dmax,umax);63     }64     return 0;65 }