刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！
简答题
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}。
对于给定的整数 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的子序列。由于数字可能非常大，我们需要对状态进行压缩。具体来说，我们可以使用状态压缩的动态规划，只保留当前需要的状态信息，从而节省内存。在实现时，我们可以使用二分查找来快速找到满足条件的状态。最后，将所有状态的数量相加即可得到答案。由于答案可能非常大，我们需要对结果取模。因此，最终的答案是所有状态数量的总和取模后的结果。
创作类型：
原创
本文链接：2.漂亮的序列对于给定的整数 m，我们称一个序列是“漂亮”的，如果它包含至少 2 个整数，并且有 2
版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！
分享考题 
