Input输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)
Output对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.
Sample Input
8 389 207 155 300 299 170 158 65
Sample Output
2
可以试着用贪心法和dp来做，
下面写出dp代码：
#include<iostream> using namespace std; const int maxn=10000; int n,high[maxn]; int LIS(){ int ans=1; int dp[maxn]; dp[1]=1; for(int i=2;i<=n;i++) { int max=0; for(int j=1;j<i;j++) if(dp[j]>max&&high[j]<high[i]) max=dp[j]; dp[i]=max+1; if(dp[i]>ans) ans=dp[i]; } return ans; } int main() { while(cin>>n){ for(int i=1;i<=n;i++) cin>>high[i]; cout<<LIS()<<endl; } }
供最长递增子序列的学习和复习。
原文：https://www.cnblogs.com/hrlsm/p/12798146.html