2022 年 3 月青少年软编等考 C 语言四级真题解析

T1. 拦截导弹

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

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

时间限制：1 s
内存限制：64 MB

• 输入
  第一行是一个整数 $N$（不超过 $15$），表示导弹数。
  第二行包含 $N$ 个整数，为导弹依次飞来的高度（雷达给出的高度数据是不大于 $30000$ 的正整数）。
• 输出
  一个整数，表示最多能拦截的导弹数。
• 样例输入

  8
  389 207 155 300 299 170 158 65
  

• 样例输出

  6
  

思路分析

此题考查动态规划中的 $\mathtt{LIS}$ 问题，属于基础题。原题来自 1999 年 NOIP 复赛。

此题显然求最长不上升子序列长度，定义 $f_i$ 表示以 $a_i$ 结尾的最长不上升子序列长度，则状态转移方程为
f i = max ⁡ { f i , f j + 1 } f_i = \max\{f_i, f_j + 1\} fi​=max{ fi​,fj​+1}

其中 $j<i$ 且 $a_j\ge a_i$，初始状态为 $f_i=1$，最终 max ⁡ { f i } \max\{f_i\} max{ fi​} 即为答案。

/*
 * Name: T1.cpp
 * Problem: 拦截导弹
 * Author: Teacher Gao.
 * Date&Time: 2024/12/15 15:22
 */

#include <iostream>

using namespace std;

int main()
{
   
	int n, a[20], f[20] = {
   0};

	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[j] >= a[i])
				f[i] = max(f[i], f[j] + 1);
		}
	}

	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans = max(ans, f[i]);

	cout << ans << endl;

	return 0;
}

T2. 神奇的数列

一个正整数数列，可以将它切割成若干个数据段，每个数据段由值相同的相邻元素构成。该数列的神奇之处在于，每次切除一个数据段后，该数据段前后的元素自动连接在一起成为邻居。例如从数列 $28977694$ 中切除数据段 $77$ 后，余下的元素会构成数列 $289694$。

请问若要将该数列切割成若干个数据段，则至少会切出来几个数据段？

时间限制：1 s
内存限制：64 MB

• 输入
  第一行是一个整数 $T$，$T\le 10$，表示共有多少组测试数据。
  每组测试数据的输入包括两行：第一行是整数 $N$，$N\le 200$，表示数列的长度，第二行是 $N$ 个正整数。
• 输出
  每个测试数据的输出占一行，是一个整数。格式是：Case n: x，$n$ 是测试数据组编号，$x$ 是答案。
• 样例输入

  2
  8
  2 8 9 7 7 6 9 4
  16
  2 8 9 7 7 6 9 4 4 2 8 4 2 7 6 9
  

• 样例输出

  Case 1: 6
  Case 2: 11
  

• 提示
  按下列顺序切割数列 $28977694$，只要切割成 $6$ 段：
  • 切割出 $77$，余下 $289694$
  • 切割出 6