简答题 偏难
#7306

拦截导弹 某国为了防御敌国的导弹袭击, 发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷: 虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不…

拦截导弹

某国为了防御敌国的导弹袭击, 发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷: 虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。 某天, 雷达捕捉到敌国的导弹来袭。 由于该系统还在试用阶段, 所以只有一套系统, 因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度(雷达给出的高度数据是不大于 30000 的正整数) , 计算这套系统最多能拦截多少导弹。

时间限制: 1000

内存限制: 65536

输入

第一行是一个整数 N(不超过 15) , 表示导弹数。 第二行包含 N 个整数, 为导弹依次飞来的高度(雷达给出的高度数据是不大于 30000的正整数) 。

输出

一个整数, 表示最多能拦截的导弹数。

样例输入

8
389 207 155 300 299 170 158 65

样例输出

6
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;bits/stdc++.h&gt; #include &lt;cmath&gt; #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; using namespace std; int n[2002], t = 1, f; int b1[2002], b2[2002], r1, r2; int main() {   int c;   cin &gt;&gt; c;   for (int i = 1; i &lt;= c; i++) {     cin &gt;&gt; n[i];   }   b1[1] = n[1];   r1 = 1;   for (int i = 2; i &lt;= c; i++) {     if (b1[r1] &gt;= n[i]) {       b1[++r1] = n[i];     } else {       *upper_bound(b1 + 1, b1 + r1 + 1, n[i], greater&lt;int&gt;()) = n[i];     }   }   cout &lt;&lt; r1 &lt;&lt; endl; }</pre>
这道题暂未补解析。