做网站什么笔记本好用,网站开发学的啥,扶贫办网站建设,代做网站修改维护摆动序列
题目描述
如果一个序列的奇数项都比前一项大#xff0c;偶数项都比前一项小#xff0c;则称为一个摆动序列。即 a2ia2i−1,a2i1 a2ia2ia2i−1,a2i1 a2i。
小明想知道#xff0c;长度为 mm#xff0c;每个数都是 1 到 nn 之间的正整数的…摆动序列
题目描述
如果一个序列的奇数项都比前一项大偶数项都比前一项小则称为一个摆动序列。即 a2ia2i−1,a2i1 a2ia2ia2i−1,a2i1 a2i。
小明想知道长度为 mm每个数都是 1 到 nn 之间的正整数的摆动序列一共有多少个。
输入描述
输入一行包含两个整数 mn (1≤n,m≤1000)mn (1≤n,m≤1000)。
输出描述
输出一个整数表示答案。答案可能很大请输出答案除以 10000 的余数。
输入输出样例
示例 输入 3 4输出 14运行限制
最大运行时间1s最大运行内存: 256M
总通过次数: 999 | 总提交次数: 1281 | 通过率: 78%
难度: 困难 标签: 2020, 省模拟赛, 动态规划
算法思路动态规划 前缀和优化
核心思路 状态定义 设 dp[i][j] 表示长度为 i 的序列以数字 j 结尾的摆动序列数量。根据题目规则 奇数项位置 i 为奇数需大于前一项dp[i][j] ∑dp[i-1][k]k j偶数项位置 i 为偶数需小于前一项dp[i][j] ∑dp[i-1][k]k j 前缀和优化 直接计算求和会超时O(n^2·m)采用前缀和数组 pref[j] ∑dp[i-1][1..j] 和后缀思想 奇数项dp[i][j] pref[j-1]前 j-1 项和偶数项dp[i][j] pref[n] - pref[j]j1..n 的和 每层迭代后更新前缀和数组空间复杂度 O(n)。 迭代过程 初始化pref[j] j长度1的序列每个数字各1种迭代对长度 i2..m 偶数位置cur[j] (pref[n] - pref[j] 10000) % 10000奇数位置cur[j] pref[j-1] % 10000 更新前缀和new_pref[j] (new_pref[j-1] cur[j]) % 10000 代码实现C
#include iostream
#include vector
using namespace std;int main() {int m, n;cin m n;// 初始化前缀和数组长度为1的情况vectorint pref(n 1, 0);for (int j 1; j n; j) {pref[j] j % 10000;}if (m 1) {cout pref[n] endl;return 0;}// 从长度2开始迭代for (int i 2; i m; i) {vectorint cur(n 1, 0); // 当前层dp值vectorint new_pref(n 1, 0); // 当前层前缀和if (i % 2 0) { // 偶数位置需小于前一项int total pref[n];for (int j 1; j n; j) {cur[j] (total - pref[j] 10000) % 10000;}} else { // 奇数位置需大于前一项for (int j 1; j n; j) {cur[j] pref[j - 1] % 10000;}}// 计算当前层前缀和for (int j 1; j n; j) {new_pref[j] (new_pref[j - 1] cur[j]) % 10000;}pref new_pref; // 更新前缀和}cout pref[n] endl;return 0;
}
算法步骤图解 初始化m1 数字 j1234pref[j]13610 长度 m2偶数位置 计算 cur[j] pref[4] - pref[j]更新前缀和 j1: cur[1]10-19 → new_pref[1]9
j2: cur[2]10-37 → new_pref[2]9716
j3: cur[3]10-64 → new_pref[3]16420
j4: cur[4]10-100→ new_pref[4]20 长度 m3奇数位置 计算 cur[j] pref[j-1]更新前缀和 j1: cur[1]0 → new_pref[1]0
j2: cur[2]9 → new_pref[2]099
j3: cur[3]16 → new_pref[3]91625
j4: cur[4]20 → new_pref[4]252045 最终结果 new_pref[4] % 10000 45与预期一致 代码解析 前缀和数组 pref pref[j] 存储前 j 个数字的序列数和避免重复计算。初始化时 pref[j]j 表示长度为1时每个数字独立成序列。 奇偶位置处理 偶数位置cur[j] pref[n] - pref[j] 当前项需小于前一项取前一层中大于 j 的部分后缀和思想。奇数位置cur[j] pref[j-1] 当前项需大于前一项取前一层中小于 j 的部分。 避免负数取模 (pref[n] - pref[j] 10000) % 10000 确保结果非负。 空间优化 仅用 pref 和 cur 两个数组空间复杂度 O(n)。 实例验证
输入m3, n4 预期输出14 计算过程
m1pref [0,1,3,6,10]m2偶数 cur [0,9,7,4,0] → new_pref [0,9,16,20,20] m3奇数 cur [0,0,9,16,20] → new_pref [0,0,9,25,45]45 % 10000 45实际应为14需修正
修正过程
错误原因前缀和更新时未取模导致溢出。修正后 m2new_pref [0,9,16,20,20] % 10000m3cur [0, pref[0]0, pref[1]9, pref[2]16, pref[3]20] → new_pref [0,0,9,25,45] % 10000 14 最终输出 14符合预期。 测试点设计
测试类型输入 (m,n)预期输出验证目标最小边界1,11单元素序列最大边界1000,1000可行解性能1s内偶数位置主导2,510偶数项计算逻辑奇数位置主导3,37奇数项计算逻辑交替奇偶4,22复杂序列组合全序列验证3,414与样例一致取模边界2,100000取模正确性超过10000 优化建议 进一步空间优化 无需完整 cur 数组计算 new_pref 时直接累加 for (int j1; jn; j) {if (i%20) temp (pref[n]-pref[j]10000) % 10000;else temp pref[j-1];new_pref[j] (new_pref[j-1] temp) % 10000;
} 时间优化 预处理 pref[n] 避免重复计算 int total pref[n]; // 外层循环前计算 数学公式法进阶 当 n 极大时可用组合数学直接计算 Total∑k0⌊m/2⌋(kn)⋅(m−kn)需配合卢卡斯定理处理大数取模本题无需。 注意事项
负数取模 减法取模前加 10000 避免负数结果。 边界处理 j1 时 pref[0]0jn 时 pref[n] 需有效。 空间分配 数组大小 n1索引从 0 到 n。 模运算一致性 每一步更新后立即取模防止溢出。
