故人何以

用户名：gurenheyi

访问量：18429

签　名：

我变秃了，也变强了

等　　级
排　　名	344
经　　验	5334
参赛次数	3
文章发表	58
年　　龄	22
在职情况	学生
学　　校
专　　业

　　自我简介：

大鹏一日同风起，扶摇直上九万里。

TA的其他文章

数学的图表-题解(C++代码)
浏览：167

你可能喜欢

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

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

　　作者: 故人何以　　　　发表时间：2019-12-31 01:28:08 浏览：2184　|　评论：3　

原题链接：蓝桥杯2014年第五届真题-波动数列

# 思路
使用递归暴力破解的话，肯定会超时。
数列 {xn}，第二项 x1 开始，每一项都会进行一次 P(+a，-b)操作，且第 n 项的操作会影响后面所有项。
![](/image_editor_upload/20191231010157_65343.png)
经过分解，数列之和 Sn = n  x + k  a - t  b。
其中，k + t = ∑(1, n - 1)。
对 k ∈ [ 0, ∑ ]，检验上述式子是否存在整数解 x，如果存在，则这个 k 值符合题目要求。
但是一个 k 值，对应多种组合。
比如，数列 X0、X1、X2、X3，若 k 值为 3，可由 X1 进行P(+a)操作，也可由 X2、X3 进行P(+a)操作。
观察上图，对 X1 进行P(+a)，产生 n-1 个(+a)，对 X2 进行P(+a)，产生 n-2 个(+a)，……，对 Xn-1 进行P(+a)，产生 1 个(+a)。
经过等效转换，即有**数组 [1, 2, 3, ……，n-1]。
选取任意个数，其和值为 k 的组合有多少？**
使用动态规划，dp[i][j] 表示前 i 个数中，和值为 j 的组合数。
递推关系，dp[i][j] = dp[i - 1][j] + dp[i - 1][j - i]。
# 细节
很容易出现内存超限、时间超限，所以要做很多优化。
# 代码
```cpp
#include <iostream>

#define MOD 100000007
typedef long long LL;

int main()
{
	int n;
	LL sn, a, b;
	std::cin >> n >> sn >> a >> b;

// 1、2、3、...、n-1 之和
	int sigma = n * (n - 1) / 2;
	// 空间优化：使用滚动数组
	LL* dp = new LL[sigma + 1];
	for (int i = 0; i <= sigma; i++)
	{
		dp[i] = 0;
	}
	// dp[1][j]
	dp[0] = dp[1] = 1;
	// 滚动求解 dp[2][j]、……、dp[n-1][j]
	for (int i = 2; i < n; i++)
	{
		// 时间优化：j 不初始化为 sigma，因为最大取值就是 1+2+...+i
		//			截止条件 j >= i，因为 dp[j] = dp[j] + dp[j-i]
		for (int j = (1 + i) * i / 2; j >= i; j--)
		{
			// ******坑******
			// 计算 dp 的时候也要记得取模，否则会发生溢出
			dp[j] = (dp[j] + dp[j - i]) % MOD;
		}
	}

// nx + ka - tb = sn，穷举 k
	LL res = 0;
	// 时间优化：预先计算好 k=0 的情况，k加一时只需 nx-a-b
	LL nx = sn + sigma * b, unit = a + b;
	for (int k = 0; k <= sigma; k++)
	{
		if (0 == nx % n)
		{
			res = (res + dp[k]) % MOD;
		}
		nx -= unit;
	}
	std::cout << res;

delete[] dp;
	return 0;
}
```
2019-12-31 01:27:57 星期二

0.0分

9 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

早起床

看了半天终于看懂了，唉，感觉没有很高天赋的初学者都是这样吧，但我又有一点很棒的天赋，只是数量少。

2022-10-05 18:20:23

虹山上峰

好难啊

2022-04-01 20:40:59

Zed

respect

2021-03-06 21:13:21

故人何以

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(3)，复杂度最低的方法没有之一！！！！！

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

printf基础练习2 （有点不明白）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C++代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

核桃的数量（C语言代码）

故人何以

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(3)，复杂度最低的方法没有之一！！！！！

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

printf基础练习2 （有点不明白）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C++代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

核桃的数量 （C语言代码）

　　评论区

核桃的数量（C语言代码）