海南网站建设推广公司,石家庄最新封闭小区消息,新乡外贸网站建设,深圳网络推广网站推广所有代码均来自于acwing中的算法基础课和算法提高课 Description 某国为了防御敌国的导弹袭击#xff0c;发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷#xff1a;虽然它的第一发炮弹能够到达任意的高度#xff0c; 但是以后每一发炮弹都不能高于前一发的高度。…所有代码均来自于acwing中的算法基础课和算法提高课 Description 某国为了防御敌国的导弹袭击发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷虽然它的第一发炮弹能够到达任意的高度 但是以后每一发炮弹都不能高于前一发的高度。某天雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段所以只有一套系统因此 有可能不能拦截所有的导弹。 Input 第一行输入M表示包含M组测试数据每组第一个输入N (N100)表示后面有N个整数表示导弹依次飞来的高度(雷达给出的高度数据是 不大于30000的正整数)。 Output 对于每组输入数据第一行输出这套系统最多能拦截多少导弹以及输出如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 Sample Input 2 7 300 250 275 252 200 138 245 7 181 205 471 782 1033 1058 1111 Sample Output 5 2 1 7 #include iostream
#include cstringusing namespace std;
const int N 110;
int a[N];
int g[N]; // 第i套系统末尾元素
int f[N]; // 以第i个元素结尾的最长非下降子序列的数量
int length; // 目前需要的系统的数量int main() {int M;cin M;while (M--) {int n;cin n;for (int i 1; i n; i) {cin a[i];}// 求最长非下降子序列的数量for (int i 1; i n ; i) {f[i]1;for (int j 1; j i ; j) {if(a[i]a[j]){f[i] max(f[i],f[j]1);}}}int result f[1];for (int i 2; i n ; i) {result max(result,f[i]);}cout result ;// 求所需要的系统的数量length 1;for (int i 1; i n; i) {int l 1, r length;while (l r) {int mid (l r 1) 1;if (a[i] g[mid]) {r mid -1;} else {l mid;}}g[r 1] a[i];length max(length, r 1);}cout length-1 endl;}
}
