第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;
}
该代码使用一个二维数组dp来保存状态,其中dp[i][j]表示序列X的前i个字符和序列Y的前j个字符的最大公共子序列的长度。
首先,将dp[i][0]和dp[0][j]都设置为0,表示当一个序列的长度为0时,最大公共子序列的长度为0。
然后,从1到m和1到n的循环遍历,如果X[i-1]等于Y[j-1],则说明X的第i个字符和Y的第j个字符相同,将dp[i][j]设置为dp[i-1][j-1]的值加1,表示当前字符可以加入最大公共子序列。
如果X[i-1]不等于Y[j-1],则说明X的第i个字符和Y的第j个字符不相同,需要在X的前i-1个字符和Y的前j个字符的最大公共子序列和X的前i个字符和Y的前j-1个字符的最大公共子序列之间取最大值,即dp[i-1][j]和dp[i][j-1]的最大值。
最后,dp[m][n]即为X和Y的最大公共子序列的长度。