编程题 共4道
兔子不吃窝边草
有谚语云：“兔子不吃窝边草”。现给定若干块排列成一条线的草皮，假设兔子从任何一块草皮开始吃，但吃完一块后，绝对不吃直接相邻的草皮，则兔子最多可以吃掉多少草？
时间限制：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
样例输出
11
4 7 9
样例2:
9
8 6 3 1
漂亮的序列
对于给定的整数 m，我们称一个序列是“漂亮”的，如果它包含至少 2 个整数，并且有 2 个相邻数字的差不超过m。你的任务是计算一个给定的 n 个正整数的序列中，有多少个子序列是漂亮的。
时间限制：6000
输入第一行给出 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}。
园林修整
园林修整中，常利用树木来形成整齐的区域分割线。园丁要将树木按高度修剪成递增或递减的形状 —— 如果一棵树太高了，就需要裁剪；如果太矮了，则需要替换。修整所花费的力气与裁剪或替换树木的数量成正比，所以需要你替他想一种最省力的修整方案。
输入第一行给出一个正个整数 N (3 ≤ N ≤ 2000)，随后一行给出 N 个正整数的树高。所有整数在区间 [1, 103] 内，同行数字间以空格分隔。
首先在一行中输出需要被裁剪或替换的树木的最少数量。第二行从左到右列出这些树木的编号（从 1 开始）。如果解不唯一，输出那个需要最少替换树木的解，题目保证这样的解是唯一的。 同行数字间必须以 1 个空格分隔，行首尾不得有多余空格。 如果没有树需要调整，则根据树高的升降性质，在一行中输出 Non-ascending（表示“非递增”）或 Non-descending（表示非递减）。
10
2 3 8 2 4 5 10 1 7 11
3
1 2 3
4
2 3 7 8
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 的树。
字母游戏
一个简单的字母游戏是这样进行的：游戏开始时，我们有两个由小写英文字母组成的串 S 和 T。两个串包含有同样的字母，只是顺序不同。换句话说，将 S 中的字母重排顺序就可以得到 T。游戏的每一步，我们可以将 S 中的任一字母移动到串头或串尾，问将 S 变换成 T 至少需要多少步？
输入分两行，先后给出字母串 S 和 T。如题面所描述的，两者包含同样的小写英文字母，只是顺序不同。每个字母串的长度不超过 1000。
在一行中输出将 S 变换成 T 至少需要的步骤数。
iononmrogdg
goodmorning
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。