第1題：攔截導(dǎo)彈

某國為了防御敵國的導(dǎo)彈襲擊， 發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。 但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷： 雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。 某天， 雷達(dá)捕捉到敵國的導(dǎo)彈來襲。 由于該系統(tǒng)還在試用階段， 所以只有一套系統(tǒng)， 因此有可能不能攔截所有的導(dǎo)彈。
輸入導(dǎo)彈依次飛來的高度(雷達(dá)給出的高度數(shù)據(jù)是不大于 30000 的正整數(shù)) ， 計算這套系統(tǒng)最多能攔截多少導(dǎo)彈。
時間限制： 1000
內(nèi)存限制： 65536
輸入
第一行是一個整數(shù) N(不超過 15) ， 表示導(dǎo)彈數(shù)。 第二行包含 N 個整數(shù)， 為導(dǎo)彈依次飛來的高度(雷達(dá)給出的高度數(shù)據(jù)是不大于 30000的正整數(shù)) 。
輸出
一個整數(shù)， 表示最多能攔截的導(dǎo)彈數(shù)。
樣例輸入
8
389 207 155 300 299 170 158 65
樣例輸出
6

要解決攔截導(dǎo)彈的問題，可以使用動態(tài)規(guī)劃的方法。

以下是使用C語言實現(xiàn)的代碼：

#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;
}

該代碼使用一個一維數(shù)組dp來保存狀態(tài)，其中dp[i]表示以第i個導(dǎo)彈為結(jié)尾的最大攔截導(dǎo)彈數(shù)。

首先，初始化dp數(shù)組的所有元素為1，表示每個導(dǎo)彈都可以單獨攔截。然后，遍歷導(dǎo)彈數(shù)組，對于每個導(dǎo)彈missiles[i]，在之前的導(dǎo)彈中查找高度小于等于當(dāng)前導(dǎo)彈的導(dǎo)彈missiles[j]，如果找到，則更新dp[i]為dp[j]+1，表示以導(dǎo)彈missiles[i]結(jié)尾的最大攔截導(dǎo)彈數(shù)。最后，找到dp數(shù)組中的最大值即為所求的最多能攔截的導(dǎo)彈數(shù)。

第2題：神奇的數(shù)列

一個正整數(shù)數(shù)列， 可以將它切割成若干個數(shù)據(jù)段， 每個數(shù)據(jù)段由值相同的相鄰元素構(gòu)成。 該數(shù)列的神奇之處在于， 每次切除一個數(shù)據(jù)段后，該數(shù)據(jù)段前后的元素自動連接在一起成為鄰居。 例如從數(shù)列“2 8 9 77 6 9 4” 中切除數(shù)據(jù)段“7 7 ” 后， 余下的元素會構(gòu)成數(shù)列“2 8 9 6 94”
請問若要將該數(shù)列切割成若干個數(shù)據(jù)段， 則至少會切出來幾個數(shù)據(jù)段?
樣例： 按下列順序切割數(shù)列“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
內(nèi)存限制： 65536
輸入
第一行是一個整數(shù)， 示共有多少組測試數(shù)據(jù)。 每組測試數(shù)據(jù)的輸入包括兩行： 第一行是整數(shù) N, N<=200,表示數(shù)列的長度， 第二行是 N 個正整數(shù)。
輸出
每個測試案例的輸出占一行， 是一個整數(shù)。 格式是： Case n: x n 是測試數(shù)據(jù)組編號， 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

要解決神奇的數(shù)列問題，可以使用貪心算法。

以下是使用C語言實現(xiàn)的代碼：

#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;
}

該代碼使用一個循環(huán)遍歷數(shù)列，對于每個數(shù)列元素sequence[i]，如果它與前一個元素sequence[i-1]不相等，則將段數(shù)segments加1。最后，segments的值即為所求的切割數(shù)據(jù)段的數(shù)量。

第3題：硬幣

宇航員 Bob 有一天來到火星上， 他有收集硬幣的習(xí)慣。 于是他將火星上所有面值的硬幣都收集起來了， 一共有 n 種， 每種只有一個： 面值分別為 a1,a2… an。 Bob 在機場看到了一個特別喜歡的禮物， 想買來送給朋友 Alice， 這個禮物的價格是 X 元。 Bob 很想知道為了買這個禮物他的哪些硬幣是必須被使用的， 即 Bob 必須放棄收集好的哪些硬幣種類。 飛機場不提供找零， 只接受恰好 X 元。
時間限制： 1000
內(nèi)存限制： 262144
輸入
第一行包含兩個正整數(shù) n 和 x。 (1 <= n <= 200, 1 <= x <= 10000) 第二行從小到大為 n 個正整數(shù) a1, a2, a3 … an (1 <= ai <= 10000)
輸出
第一行是一個整數(shù)， 即有多少種硬幣是必須被使用的。 第二行是這些必須使用的硬幣的面值(從小到大排列) 。
樣例輸入
5 18
1 2 3 5 10
樣例輸出
2
5 10
提示
輸入數(shù)據(jù)將保證給定面值的硬幣中至少有一種組合能恰好能夠支付 X元。 如果不存在必須被使用的硬幣， 則第一行輸出 0， 第二行輸出空行。

要解決硬幣問題，可以使用動態(tài)規(guī)劃的方法。

以下是使用C語言實現(xiàn)的代碼：

#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;
}

該代碼使用一個布爾數(shù)組dp來保存狀態(tài)，其中dp[i]表示是否存在一種硬幣組合，可以湊出金額i。

首先，將dp[0]設(shè)置為true，表示金額為0時不需要使用任何硬幣。然后，遍歷硬幣數(shù)組coins，對于每個硬幣coins[i]，從amount向前遍歷到coins[i]，如果存在一種硬幣組合可以湊出金額j-coins[i]，則說明存在一種硬幣組合可以湊出金額j，將dp[j]設(shè)置為true。

最后，統(tǒng)計dp數(shù)組中為true的元素個數(shù)，即為必須被使用的硬幣種類的數(shù)量。并輸出這些必須使用的硬幣面值。

第4題：公共子序列

我們稱序列 Z = < z1, z2, …, zk >是序列 X = < x1, x2, …, xm >的子序列當(dāng)且僅當(dāng)存在 嚴(yán)格上升 的序列< i1, i2, …, ik >， 使得對 j = 1, 2, … ,k, 有xij = zj。 比如 Z = < a, b, f, c > 是 X = < a, b, c, f, b, c >的子序列。 現(xiàn)在給出兩個序列 X 和 Y， 你的任務(wù)是找到 X 和 Y 的最大公共子序列， 也就是說要找到一個最長的序列 Z， 使得 Z 既是 X 的子序列也是 Y 的子序列。
時間限制： 3000
內(nèi)存限制： 65536
輸入
輸入包括多組測試數(shù)據(jù)。 每組數(shù)據(jù)包括一行， 給出兩個長度不超過200 的字符串， 表示兩個序列。 兩個字符串之間由若干個空格隔開。
輸出
對每組輸入數(shù)據(jù)， 輸出一行， 給出兩個序列的最大公共子序列的長度。
樣例輸入
abcfbc abfcab
programming contest
abcd mnp
樣例輸出
4
2
0

要解決最大公共子序列問題，可以使用動態(tài)規(guī)劃的方法。

以下是使用C語言實現(xiàn)的代碼：

#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;
}

該代碼使用一個二維數(shù)組dp來保存狀態(tài)，其中dp[i][j]表示序列X的前i個字符和序列Y的前j個字符的最大公共子序列的長度。

首先，將dp[i][0]和dp[0][j]都設(shè)置為0，表示當(dāng)一個序列的長度為0時，最大公共子序列的長度為0。

然后，從1到m和1到n的循環(huán)遍歷，如果X[i-1]等于Y[j-1]，則說明X的第i個字符和Y的第j個字符相同，將dp[i][j]設(shè)置為dp[i-1][j-1]的值加1，表示當(dāng)前字符可以加入最大公共子序列。

如果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的最大公共子序列的長度。