蓝桥杯2014年第五届真题-波动数列-题解(C语言代码)

浅梦逸尘 1年前 回复TA

/*解题思路：
设数列首项为 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;

短发及腰 4年前 回复TA

配上注释就好了

短发及腰 4年前 回复TA

@优雅永不过时 配上注释就好了

优雅永不过时 4年前 回复TA

求解释

发表评论 取消回复