原题链接：蓝桥杯2014年第五届真题-波动数列
0.0分
6 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
/*解题思路： 设数列首项为 x，后续每项的变化量为 d₁,d₂,...,dₙ₋₁（每个 d 只能是 +a 或 -b） 则数列总和可表示为：s = n*x + (d₁*(n-1) + d₂*(n-2) + ... + dₙ₋₁*1) 通过变形推导，可将问题转化为统计满足条件的变化量组合数，使用动态规划实现*/ #include <stdio.h> #include <stdlib.h> int main(void) { // 变量定义： // n：数列长度；s：数列总和；a：增量；b：减量；number：符合条件的数列总数 long long n = 0, s = 0, a = 0, b = 0, number = 0; // i,j：循环控制变量；x：用于判断首项是否为整数；max：最大可能的加权和步数 long long i = 0, j = 0, x = 0, max = 0; // 动态规划数组，list[k]表示"加权和步数为k"的变化量组合方案数 long long *list = NULL; // 读取输入数据：数列长度、目标总和、增量、减量 scanf("%lld %lld %lld %lld", &n, &s, &a, &b); // 计算最大加权和步数：1+2+...+(n-1) = n*(n-1)/2 // 这里的"步数"对应变化量被加权求和的系数总和 max = (n * (n - 1)) / 2; // 分配动态规划数组，大小为max+1（包含0到max的所有可能值） // calloc初始化会将所有元素置0，便于后续累加 list = (long long*)calloc((max + 1), sizeof(long long)); // 边界条件： // list[0] = 1 表示"0步"只有1种方案（不选任何增量） // list[1] = 1 表示"1步"只有1种方案（选择第一个位置的增量） list[0] = list[1] = 1;