一、简答题
1、1.兔子不吃窝边草
有谚语云：“兔子不吃窝边草”。现给定若干块排列成一条线的草皮，假设兔子从任何一块草皮开始吃，但吃完一块后，绝对不吃直接相邻的草皮，则兔子最多可以吃掉多少草？
时间限制：10000
内存限制：65536
输入
输入第一行给出两个正整数，即 N (≤ 105) 为草皮的块数、 i (1 ≤ i ≤ N) 为兔子开始吃的第一块草皮的编号。第二行给出 N 个正整数 (≤ 103)，以空格分隔，依次表示每块草皮的含草量。
输出
首先在一行中输出这只兔子最多可以吃掉的草量。下一行按兔子吃草的顺序输出每块被吃掉的草皮的编号。同行数字以 1 个空格分隔，行首尾不得有多余空格。 注意：我们必须假设兔子只朝一个方向跳着吃草，否则如果它可以来回跳，就能吃掉所有的草了。如果朝左右两个方向得到的结果一样，则兔子总是喜欢向左边跳；并且如果有多块草皮都可以得到同样的结果，兔子总是选择跳到离自己最近的那块。
样例输入
样例1：
10 4
2 1 4 3 1 1 5 2 3 1
样例2：
10 8
2 1 4 3 1 1 5 2 3 1
样例输出
样例1：
11
4 7 9
样例2:
9
8 6 3 1
解析：
这道题目是一个典型的动态规划问题。动态规划是一种求解最优化问题的方法，其基本思想是将问题分解为若干个子问题，通过求解子问题的最优解，逐步构造出原问题的最优解。在这道题目中，我们可以将问题分解为求解以每块草皮为结尾的最长不连续草皮序列的长度，然后通过比较和选择得到最优解。
具体的实现过程中，我们需要使用动态规划的思想，通过状态转移方程来计算dp值，并在遍历过程中记录最大的dp值和对应的草皮编号。由于题目中限制了内存和时间的限制，我们需要使用高效的算法来求解。动态规划是一种非常有效的求解最优化问题的方法，能够在较短的时间内得到最优解。
2、2.漂亮的序列
对于给定的整数 m，我们称一个序列是“漂亮”的，如果它包含至少 2 个整数，并且有 2 个相邻数字的差不超过m。你的任务是计算一个给定的 n 个正整数的序列中，有多少个子序列是漂亮的。
时间限制：6000
内存限制：65536
输入
输入第一行给出 2 个正整数 n 和 m (2 ≤ n ≤ 105, 1 ≤ m ≤ 103)，随后一行给出序列中 n 个不超过 105 的正整数。同行数字间以空格分隔。
输出
输出原始序列中漂亮子序列的个数。因为答案可能非常大，所以你需要输出对 1000000007 (109 + 7) 取模后的结果。
样例输入
4 2
5 3 8 6
样例输出
8
提示
样例解释：
1、子序列下标为 {1, 2}, 对应值为 {5, 3}；
2、子序列下标为 {1, 4}, 对应值为 {5, 6}；
3、子序列下标为 {3, 4}, 对应值为 {8, 6}；
4、子序列下标为 {1, 2, 3}, 对应值为 {5, 3, 8}；
5、子序列下标为 {1, 2, 4}, 对应值为 {5, 3, 6}；
6、子序列下标为 {1, 3, 4}, 对应值为 {5, 8, 6}；
7、子序列下标为 {2, 3, 4}, 对应值为 {3, 8, 6}；
8、子序列下标为 {1, 2, 3, 4}, 对应值为 {5, 3, 8, 6}。
解析：
这个问题可以通过动态规划来解决。我们可以定义一个状态数组dp，其中dp[i]表示以第i个数结尾的漂亮子序列的数量。对于序列中的每个数，我们需要考虑两种情况：单独作为子序列，或者作为已有漂亮子序列的延续。对于第二种情况，我们需要查找在前面的数中，哪些数与我们当前处理的数构成的差不超过m的子序列。由于数字可能非常大，我们需要对状态进行压缩。具体来说，我们可以使用状态压缩的动态规划，只保留当前需要的状态信息，从而节省内存。在实现时，我们可以使用二分查找来快速找到满足条件的状态。最后，将所有状态的数量相加即可得到答案。由于答案可能非常大，我们需要对结果取模。因此，最终的答案是所有状态数量的总和取模后的结果。
3、3.园林修整
园林修整中，常利用树木来形成整齐的区域分割线。园丁要将树木按高度修剪成递增或递减的形状 —— 如果一棵树太高了，就需要裁剪；如果太矮了，则需要替换。修整所花费的力气与裁剪或替换树木的数量成正比，所以需要你替他想一种最省力的修整方案。
时间限制：10000
内存限制：65536
输入
输入第一行给出一个正个整数 N (3 ≤ N ≤ 2000)，随后一行给出 N 个正整数的树高。所有整数在区间 [1, 103] 内，同行数字间以空格分隔。
输出
首先在一行中输出需要被裁剪或替换的树木的最少数量。第二行从左到右列出这些树木的编号（从 1 开始）。如果解不唯一，输出那个需要最少替换树木的解，题目保证这样的解是唯一的。 同行数字间必须以 1 个空格分隔，行首尾不得有多余空格。 如果没有树需要调整，则根据树高的升降性质，在一行中输出 Non-ascending（表示“非递增”）或 Non-descending（表示非递减）。
样例输入
样例1：
10
2 3 8 2 4 5 10 1 7 11
样例2：
3
1 2 3
样例输出
样例1：
4
2 3 7 8
样例2：
Non-descending
提示
样例1解释： 首先，要将树木修整成按高度非递减的样式，我们需要调整 4 棵树；而要修整成非递增样式，则需要调整 7 棵树。所以我们应选择递增序列对应的解。 其次，存在 4 种不同的递增序列解：
1、保持树高为 2、3、4、5、10、11 的树不变，我们需要替换掉高度为 2、1、7 的 3 棵树，因为它们太矮了；
2、保持树高为 2、3、4、5、7、11 的树不变，我们需要替换掉高度为 2、1 的 2 棵树；
3、保持树高为 2、2、4、5、10、11 的树不变，我们需要替换掉高度为 1、7 的 2 棵树；
4、保持树高为 2、2、4、5、7、11 的树不变，我们只需要替换掉高度为 1 的 1 棵树。 所以最后选择输出第(4)组解，即裁剪编号为 2、3、7（对应高度为 3、8、10）的树，替换掉第 8 棵高度为 1 的树。
解析：
首先读取输入，获取树的数量和每个树的高度。对树的高度进行排序，然后遍历排序后的数组。在遍历过程中，我们维护一个变量来记录当前位置的树是否需要裁剪或替换。如果当前树的高度大于前一个树的高度，并且需要裁剪或替换操作，则累加操作次数，并记录需要裁剪或替换的树的编号。如果遍历完整个数组后，没有树需要调整，则输出Non-ascending或Non-descending表示树的高度是非递增或非递减的。否则，输出裁剪次数和需要裁剪的树的编号。为了得到最优解，我们需要按照题目要求的规则选择裁剪还是替换操作，即优先选择裁剪操作。在实现过程中，我们可以使用一个布尔数组来记录每个树是否需要裁剪或替换，然后遍历整个数组并记录需要操作的树的编号。最后输出操作次数和需要操作的树的编号即可。
时间复杂度为O(nlogn)，其中n为树的数量。因为我们需要对树的高度进行排序，排序的时间复杂度为O(nlogn)。然后我们需要遍历整个排序后的数组一次，时间复杂度为O(n)。因此总的时间复杂度为O(nlogn)。
4、4.字母游戏
一个简单的字母游戏是这样进行的：游戏开始时，我们有两个由小写英文字母组成的串 S 和 T。两个串包含有同样的字母，只是顺序不同。换句话说，将 S 中的字母重排顺序就可以得到 T。游戏的每一步，我们可以将 S 中的任一字母移动到串头或串尾，问将 S 变换成 T 至少需要多少步？
时间限制：6000
内存限制：65536
输入
输入分两行，先后给出字母串 S 和 T。如题面所描述的，两者包含同样的小写英文字母，只是顺序不同。每个字母串的长度不超过 1000。
输出
在一行中输出将 S 变换成 T 至少需要的步骤数。
样例输入
iononmrogdg
goodmorning
样例输出
8
提示
样例解释：
1、 从 iononmrogdg 开始；
2、 将最后一个 g 移动到串头: giononmrogd；
3、 将 m 移动到串尾: giononrogdm；
4、 将第一个 o 移动到串尾: ginonrogdmo；
5、 将 r 移动到串尾: ginonogdmor；
6、 将第一个 n 移动到串尾: gionogdmorn；
7、 将 i 移动到串尾: gonogdmorni；
8、 将第一个 n 移动到串尾: googdmornin；
9、 将第二个 g 移动到串尾: goodmorning。
解析：
{这个问题可以通过动态规划来解决。我们可以定义一个二维数组dp，其中dp[i][j]表示将字符串S的前i个字符变成字符串T的前j个字符所需的最小步数。我们可以从字符串的开头开始逐步计算，逐步填充dp数组。对于每一对字符S[i]和T[j]，我们需要考虑两种情况：如果S[i]等于T[j]，那么我们可以直接将S中的下一个字符移动到T中的下一个位置，此时需要的步数为dp[i-1][j-1]；如果S[i]不等于T[j]，我们需要考虑将S中的某个字符移动到T中的这个位置，此时需要的步数为dp[i-k][j]（其中k为字符串中S到T的最长公共前缀长度）。因此，我们可以通过动态规划的方式计算出最少步数。最终答案即为dp[S的长度][T的长度]。}
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
