在这里插入图片描述

第1题：最长上升子序列

一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8). 你的任务，就是对于给定的序列，求出最长上升子序列的长度。
时间限制：11000
内存限制：65536
输入
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。
输出
最长上升子序列的长度。
样例输入
7
1 7 3 5 9 4 8
样例输出
4

要解决最长上升子序列的问题，可以使用动态规划的方法。

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

#include <stdio.h>
#include <stdlib.h>int max(int a, int b) {return (a > b) ? a : b;
}int longestIncreasingSubsequence(int arr[], int n) {int dp[1001] = {0};int maxLen = 1;for (int i = 0; i < n; i++) {dp[i] = 1;for (int j = 0; j < i; j++) {if (arr[i] > arr[j]) {dp[i] = max(dp[i], dp[j] + 1);}}maxLen = max(maxLen, dp[i]);}return maxLen;
}int main() {int n;scanf("%d", &n);int arr[1001];for (int i = 0; i < n; i++) {scanf("%d", &arr[i]);}int longestLen = longestIncreasingSubsequence(arr, n);printf("%d\n", longestLen);return 0;
}

该代码使用一个一维数组dp来记录以每个位置上的元素为结尾的最长上升子序列的长度。

首先，将dp数组的初始值全部设为1，因为任意单个元素本身就是一个长度为1的上升子序列。

然后，从第二个位置开始，遍历数组中的每个元素，对于每个元素，再次遍历它之前的元素，如果找到比当前元素小的元素，说明可以将当前元素加入到以该元素结尾的子序列中，更新dp数组的值。

最后，遍历dp数组找到最大的值，即为最长上升子序列的长度。

第2题：神奇的口袋

有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。John现在有n个想要得到的物品，每个物品的体积分别是a1，a2……an。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式。
时间限制：10000
内存限制：65536
输入
输入的第一行是正整数n (1 <= n <= 20)，表示不同的物品的数目。接下来的n行，每行有一个1到40之间的正整数，分别给出a1，a2……an的值。
输出
输出不同的选择物品的方式的数目。
样例输入
3
20
20
20
样例输出
3

要解决神奇的口袋问题，可以使用递归的方法进行求解。

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

#include <stdio.h>int count = 0;void magicalPocket(int items[], int n, int idx, int sum) {if (sum == 0) {count++;return;}if (idx == n || sum < 0) {return;}magicalPocket(items, n, idx + 1, sum - items[idx]);magicalPocket(items, n, idx + 1, sum);
}int main() {int n;scanf("%d", &n);int items[21];for (int i = 0; i < n; i++) {scanf("%d", &items[i]);}magicalPocket(items, n, 0, 40);printf("%d\n", count);return 0;
}

该代码使用递归函数magicalPocket来尝试不同的选择物品的方式。

递归函数的参数包括物品数组items、物品数量n、当前处理的物品索引idx和目标总体积sum。

函数首先判断如果目标总体积为0，则表示找到一种选择方式，将count计数器加1并返回。

然后判断如果当前处理的物品索引为n或目标总体积小于0，则返回。

接下来，递归调用函数，分为两种情况：选择当前物品或不选择当前物品。

选择当前物品时，递归调用函数并更新目标总体积为sum - items[idx]，同时将物品索引加1。

不选择当前物品时，递归调用函数并保持目标总体积为sum，同时将物品索引加1。

最后，主函数调用magicalPocket函数，并输出count计数器的值，即为不同的选择物品的方式的数目。

第3题：滑雪

Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上，这是最长的一条。
时间限制：1000
内存限制：65536
输入
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
输出
输出最长区域的长度。
样例输入
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
样例输出
25

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

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

#include <stdio.h>
#include <stdbool.h>int max(int a, int b) {return (a > b) ? a : b;
}int longestSlide(int grid[][100], int R, int C, int r, int c, int dp[][100]) {if (dp[r][c] != -1) {return dp[r][c];}int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int maxLen = 1;for (int i = 0; i < 4; i++) {int newRow = r + directions[i][0];int newCol = c + directions[i][1];if (newRow >= 0 && newRow < R && newCol >= 0 && newCol < C && grid[newRow][newCol] < grid[r][c]) {maxLen = max(maxLen, longestSlide(grid, R, C, newRow, newCol, dp) + 1);}}dp[r][c] = maxLen;return maxLen;
}int main() {int R, C;scanf("%d %d", &R, &C);int grid[100][100];int dp[100][100];for (int i = 0; i < R; i++) {for (int j = 0; j < C; j++) {scanf("%d", &grid[i][j]);dp[i][j] = -1;}}int maxLength = 0;for (int i = 0; i < R; i++) {for (int j = 0; j < C; j++) {maxLength = max(maxLength, longestSlide(grid, R, C, i, j, dp));}}printf("%d\n", maxLength);return 0;
}

该代码使用一个二维数组dp来记录从每个位置开始的最长滑坡的长度，以避免重复计算。

首先，将dp数组的初始值全部设为-1，表示尚未计算。

然后，遍历输入的区域二维数组，对于每个位置(r, c)，调用longestSlide函数进行递归计算以该位置为起点的最长滑坡长度。

在longestSlide函数中，首先判断如果dp[r][c]已经计算过，则直接返回其值。

然后，定义四个方向的移动数组directions，分别为上、下、左、右。

接下来，遍历四个方向，计算新的行和列的位置，并判断新位置是否在合法范围内且高度小于当前位置的高度。

如果满足条件，则递归调用longestSlide函数并更新maxLen的值。

最后，将dp[r][c]设为maxLen并返回。

最后，主函数遍历整个区域二维数组，找到最大的滑坡长度，并输出。

第4题：删除数字

娇娇一年级了，刚刚学会了识数和比大小。有一天，她在黑板上写上了一串数字：2，1，2，5，4。接着她擦掉了第一个2，发现剩下1，2，4都在自己的位置上，即：1在第1位，2在第2位，4在第4位。
娇娇希望擦掉某些数后，剩下的数列中在自己位置上的数尽量多。她发现这个问题很有趣，想知道最多能有几个数在自己的位置上，请你帮帮她!
时间限制：1000
内存限制：65536
输入
第一行，一个整数 TestNum( ≤ 10)，表示测试数据的组数。接下来每组数据有两行，第一行：一个整数n( ≤ 1000)，第二行：n个正整数(≤ 1000)。
输出
对于每组测试数据，输出一个数表示答案。
样例输入
3
5
2 1 2 5 4
7
2 2 3 2 4 5 3
10
1 1 2 2 3 3 4 4 5 5
样例输出
3
4
5
提示
第一组测试数据：擦掉第一个数，1 2 4 有 3 个数在自己的位置上。
第二组测试数据：擦掉第4个、第7个数，2 3 4 5 有 4 个数在自己的位置上。
第三组测试数据：每种相同的数擦掉一个，1 2 3 4 5 有 5 个数在自己的位置上。

要解决删除数字的问题，可以使用贪心算法的思路。

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

#include <stdio.h>
#include <stdbool.h>int max(int a, int b) {return (a > b) ? a : b;
}int countNumbers(int numbers[], int n) {int count = 0;for (int i = 0; i < n; i++) {if (numbers[i] == i + 1) {count++;}}return count;
}int maxCountNumbers(int numbers[], int n) {int maxCount = 0;for (int i = 0; i < n; i++) {int temp = numbers[i];numbers[i] = -1;maxCount = max(maxCount, countNumbers(numbers, n));numbers[i] = temp;}return maxCount;
}int main() {int TestNum;scanf("%d", &TestNum);while (TestNum--) {int n;scanf("%d", &n);int numbers[1000];for (int i = 0; i < n; i++) {scanf("%d", &numbers[i]);}int result = maxCountNumbers(numbers, n);printf("%d\n", result);}return 0;
}