第1题：拦截导弹

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度(雷达给出的高度数据是不大于 30000 的正整数) ，计算这套系统最多能拦截多少导弹。
时间限制： 1000
内存限制： 65536
输入
第一行是一个整数 N(不超过 15) ，表示导弹数。第二行包含 N 个整数，为导弹依次飞来的高度(雷达给出的高度数据是不大于 30000的正整数) 。
输出
一个整数，表示最多能拦截的导弹数。
样例输入
8
389 207 155 300 299 170 158 65
样例输出
6

要解决拦截导弹的问题，可以使用动态规划的方法。

以下是使用C语言实现的代码：

#include <stdio.h>#define MAX_MISSILES 15int max(int a, int b) {return (a > b) ? a : b;
}int missileInterception(int missiles[], int n) {int dp[MAX_MISSILES] = {0};int maxInterceptions = 0;for (int i = 0; i < n; i++) {dp[i] = 1;for (int j = 0; j < i; j++) {if (missiles[i] <= missiles[j]) {dp[i] = max(dp[i], dp[j] + 1);}}maxInterceptions = max(maxInterceptions, dp[i]);}return maxInterceptions;
}int main() {int n;scanf("%d", &n);int missiles[MAX_MISSILES];for (int i = 0; i < n; i++) {scanf("%d", &missiles[i]);}int maxInterceptions = missileInterception(missiles, n);printf("%d\n", maxInterceptions);return 0;
}

该代码使用一个一维数组dp来保存状态，其中dp[i]表示以第i个导弹为结尾的最大拦截导弹数。

首先，初始化dp数组的所有元素为1，表示每个导弹都可以单独拦截。然后，遍历导弹数组，对于每个导弹missiles[i]，在之前的导弹中查找高度小于等于当前导弹的导弹missiles[j]，如果找到，则更新dp[i]为dp[j]+1，表示以导弹missiles[i]结尾的最大拦截导弹数。最后，找到dp数组中的最大值即为所求的最多能拦截的导弹数。

第2题：神奇的数列

一个正整数数列，可以将它切割成若干个数据段，每个数据段由值相同的相邻元素构成。该数列的神奇之处在于，每次切除一个数据段后，该数据段前后的元素自动连接在一起成为邻居。例如从数列“2 8 9 77 6 9 4” 中切除数据段“7 7 ” 后，余下的元素会构成数列“2 8 9 6 94”
请问若要将该数列切割成若干个数据段，则至少会切出来几个数据段?
样例：按下列顺序切割数列“2 8 9 7 7 6 9 4” ，只要切割成 6 段
切割出“7 7” ，余下 “2 8 9 6 9 4”
切割出 “6” ，余下 “2 8 9 9 4”
切割出 “9 9” ，余下 “2 8 4”
切割出 “2” ，余下 “8 4”
切割出 “8” ，余下 “4”
时间限制： 1000
内存限制： 65536
输入
第一行是一个整数，示共有多少组测试数据。每组测试数据的输入包括两行：第一行是整数 N, N<=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

要解决神奇的数列问题，可以使用贪心算法。

以下是使用C语言实现的代码：

#include <stdio.h>#define MAX_LENGTH 200int min(int a, int b) {return (a < b) ? a : b;
}int countSegments(int sequence[], int n) {int segments = 1;for (int i = 1; i < n; i++) {if (sequence[i] != sequence[i - 1]) {segments++;}}return segments;
}int main() {int t;scanf("%d", &t);for (int i = 1; i <= t; i++) {int n;scanf("%d", &n);int sequence[MAX_LENGTH];for (int j = 0; j < n; j++) {scanf("%d", &sequence[j]);}int segments = countSegments(sequence, n);printf("Case %d: %d\n", i, segments);}return 0;
}

该代码使用一个循环遍历数列，对于每个数列元素sequence[i]，如果它与前一个元素sequence[i-1]不相等，则将段数segments加1。最后，segments的值即为所求的切割数据段的数量。

第3题：硬币

宇航员 Bob 有一天来到火星上，他有收集硬币的习惯。于是他将火星上所有面值的硬币都收集起来了，一共有 n 种，每种只有一个：面值分别为 a1,a2… an。 Bob 在机场看到了一个特别喜欢的礼物，想买来送给朋友 Alice，这个礼物的价格是 X 元。 Bob 很想知道为了买这个礼物他的哪些硬币是必须被使用的，即 Bob 必须放弃收集好的哪些硬币种类。飞机场不提供找零，只接受恰好 X 元。
时间限制： 1000
内存限制： 262144
输入
第一行包含两个正整数 n 和 x。 (1 <= n <= 200, 1 <= x <= 10000) 第二行从小到大为 n 个正整数 a1, a2, a3 … an (1 <= ai <= 10000)
输出
第一行是一个整数，即有多少种硬币是必须被使用的。第二行是这些必须使用的硬币的面值(从小到大排列) 。
样例输入
5 18
1 2 3 5 10
样例输出
2
5 10
提示
输入数据将保证给定面值的硬币中至少有一种组合能恰好能够支付 X元。如果不存在必须被使用的硬币，则第一行输出 0，第二行输出空行。

要解决硬币问题，可以使用动态规划的方法。

以下是使用C语言实现的代码：

#include <stdio.h>
#include <stdbool.h>#define MAX_COINS 200
#define MAX_AMOUNT 10000bool dp[MAX_AMOUNT + 1] = {false};void findCoins(int coins[], int n, int amount) {dp[0] = true;for (int i = 0; i < n; i++) {for (int j = amount; j >= coins[i]; j--) {if (dp[j - coins[i]]) {dp[j] = true;}}}
}int main() {int n, amount;scanf("%d %d", &n, &amount);int coins[MAX_COINS];for (int i = 0; i < n; i++) {scanf("%d", &coins[i]);}findCoins(coins, n, amount);int count = 0;for (int i = 1; i <= amount; i++) {if (dp[i]) {count++;}}printf("%d\n", count);for (int i = 1; i <= amount; i++) {if (dp[i]) {printf("%d ", i);}}printf("\n");return 0;
}

该代码使用一个布尔数组dp来保存状态，其中dp[i]表示是否存在一种硬币组合，可以凑出金额i。

首先，将dp[0]设置为true，表示金额为0时不需要使用任何硬币。然后，遍历硬币数组coins，对于每个硬币coins[i]，从amount向前遍历到coins[i]，如果存在一种硬币组合可以凑出金额j-coins[i]，则说明存在一种硬币组合可以凑出金额j，将dp[j]设置为true。

最后，统计dp数组中为true的元素个数，即为必须被使用的硬币种类的数量。并输出这些必须使用的硬币面值。

第4题：公共子序列

我们称序列 Z = < z1, z2, …, zk >是序列 X = < x1, x2, …, xm >的子序列当且仅当存在严格上升的序列< i1, i2, …, ik >，使得对 j = 1, 2, … ,k, 有xij = zj。比如 Z = < a, b, f, c > 是 X = < a, b, c, f, b, c >的子序列。现在给出两个序列 X 和 Y，你的任务是找到 X 和 Y 的最大公共子序列，也就是说要找到一个最长的序列 Z，使得 Z 既是 X 的子序列也是 Y 的子序列。
时间限制： 3000
内存限制： 65536
输入
输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200 的字符串，表示两个序列。两个字符串之间由若干个空格隔开。
输出
对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。
样例输入
abcfbc abfcab
programming contest
abcd mnp
样例输出
4
2
0

要解决最大公共子序列问题，可以使用动态规划的方法。

以下是使用C语言实现的代码：

#include <stdio.h>
#include <string.h>#define MAX_LENGTH 200int max(int a, int b) {return (a > b) ? a : b;
}int longestCommonSubsequence(char X[], char Y[], int m, int n) {int dp[MAX_LENGTH + 1][MAX_LENGTH + 1];for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0 || j == 0) {dp[i][j] = 0;} else if (X[i - 1] == Y[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];
}int main() {char X[MAX_LENGTH + 1];char Y[MAX_LENGTH + 1];while (scanf("%s %s", X, Y) != EOF) {int m = strlen(X);int n = strlen(Y);int length = longestCommonSubsequence(X, Y, m, n);printf("%d\n", length);}return 0;
}