第二行,输入k个正整数,表示k枚导弹的高度,按来袭导弹的袭击时间顺序给出,以空格分隔。
6
思路:
我们可以采用倒推的方法,也就是说,从最后一枚导弹开始,如果只有那一枚,显然拦截量为f[1] = 1,再往前看一枚,现在一共有2枚导弹,如果前面那枚比后面的飞得低,那么f[2] = f[1] + 1,......可以想象,每次往前加一枚导弹,射击该导弹的最大拦截量f[i]为f[i-1] + 1,也就是说只要找到i-1枚导弹中拦截量最大且比第i枚低的导弹,然后再把它拦截的导弹数加一即可...当然,必须设置一个初始值为0,如果没有,那么最大拦截量就为0 + 1了。
代码如下:
#include<iostream> using namespace std; int main() { int n; cin>>n; int a[50]; for(int i=0;i<n;i++) cin>>a[i]; int k=n-2; int c[n]; while(k>=0) { c[n-1]=1; int max(0); for(int i=n-1;i>k;i--) { if(a[k]>=a[i]&&c[i]>max) max=c[i]; } c[k]=max+1; k--; } int max(1); for(int i=0;i<n;i++) { if(c[i]>max) max=c[i]; } cout<<max; return 0; }