LikeWater

用户名：dotcpp0632461

访问量：1351

签　名：

KaMi

等　　级
排　　名	504
经　　验	3991
参赛次数	0
文章发表	90
年　　龄	0
在职情况	学生
学　　校	长江大学
专　　业	电子信息

　　自我简介：

TA的其他文章

LikeWater - 1094: 字符串的输入输出处理
浏览：6

LikeWater - 1095: The 3n + 1 problem
浏览：5

LikeWater - 1096: Minesweeper（这个题目有意思，我非常愿意为它写题解~）
浏览：11

你可能喜欢

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

LikeWater - 1449: 蓝桥杯2014年第五届真题-波动数列C++（动态规划求解）

　　作者: LikeWater　　　　发表时间：2023-03-09 21:44:39 浏览：103　|　评论：1　

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

####解题思路
1、根据题意，直接反应是利用DFS，但数据量太大，不允许，转而使用动态规划。

2、按照大佬的思路 (网址：[CSDN](https://blog.csdn.net/Haha_Sugar/article/details/123651777 "CSDN"))，使用了动态规划解题。大致思路如下：

3、将相邻两项之间的操作看作是一个封装P，P中含有两个操作，即
`P(+a,-b)`
因此，可以将前n项之和为s的数列写作满足方程：
`x+(x+P)+(x+P+P)+...+(x+(n-1)P) = s` 
合并同类项后可以写作
`nx+(P+2P+3P+...+(n-1)P) = s`
利用等差数列对P前面的系数求和得到
`nx+n(n-1)P/2 = s；`
由于P是封装，它实际是由**numa个+a、numb个-b**组合而成的，因此，上式又可以变更为
`nx+numa*a-numb*b = s` 且 `numa+numb = n*(n-1)/2；`
对**numa**进行枚举，当**numa**确定时，**numb**即确定，随即可根据上式求出x的值（即某个符合要求的序列的第一个元素的值）；
4、当x确定，+a和-b操作的排序不同会产生多种不同的种类数，因此接下来需要对排列可能的数目进行求解，这里就需要用到动态规划了。
首先，在二维数组中分析dp[i][j]，i代表第i位数字，j代表**numa**的数目，dp[i][j]存储的值代表如果有i位数字，那么j个+a的组合数目，可以得到状态转移方程：
![](/image_editor_upload/20230309/20230309093746_37880.jpg)

***（对状态转移方程的解释：每当增加了第i位数，如果它由前一个数+a得到，那么对i位数组成的数列而言，所消耗+a将会多出i个，因此有dp[i-1][j-i]这一项；如果它与前一个数之间的关系不是+a，那么有dp[i-1][j]）***
但是，如果只是用二维的动态转移矩阵求解dp[n][numa]时，发现numa的上限等于n×(n-1)/2，该题n可以多达1000，dp大小可以到（1001×499501），显然，内存会超限；因此，需要使用滚动数组代替二维的转移矩阵。滚动数组赋予i=1初值后，从右到左更新，动态转移方程可以写为：
   ** d p [ j ] = d p [ j − i ] + d p [ j ]**
根据以上分析，解题思路是，首先生成一个dp[n*(n-1)/2+1]的矩阵，存储“当位数为n时，不同的numa个数对应的组合数目”；之后枚举**numa**，取符合要求的**numa**（使得x算出来是整数）所对应的dp中的组合数目计入num，最后输出num（注意即时取余数）。

```c
#include<stdio.h>
#define MOD 100000007
int dp[500001];//numa可能的最大个数

void create(int n){
    int i,j;
    dp[0] = 1;
    for (i=1;i<n;i++)//位数
        for (j=(i*(i+1)/2);j>=i;j--)//滚动数组，从后到前更新j>=i的部分
            dp[j] = (dp[j-i]+dp[j])%MOD;//表示当numa=i的时候，n位数列+a的组合数目
}

int main()
{
	long int n,s,a,b,i,j,temp,x,num=0;
	scanf("%ld %ld %ld %ld",&n,&s,&a,&b);
	long int t = n*(n-1)/2;//numa+numb = n*(n-1)/2
	create(n);
	for (i=t;i>=0;i--) //i代表numa
	{
	    j = t-i;
	    temp = s-i*a+j*b;
	    if (temp%n==0) //x=(s-numa*a+numb*b)/n，x是整数
	    {
	        num+=(dp[i]%MOD);//+a的位置定下了，-b一定确定了
	        num%=MOD;
	    }
	}
	printf("%ld",num);
	return 0;
}

```
###以上转载自 CSDN:一只干饭猿 ，写的很好，分享给大家！

0.0分

2 人评分

C语言网提供「C语言、C++、算法竞赛、真题百练、Python课程」在线课程，全部由资深研发工程师或ACM金牌大佬亲授课，更科学、全面的课程体系，以在线视频+在线评测的学习模式学习，学练同步，拒绝理论派，真正学会编程！还有奖学金等增值福利等你！

　　评论区

LikeWater

6666666666666还得是CSDN大佬，困惑许久的动态规划终于理解一点了

2023-03-09 21:45:13 | |

LikeWater

TA的其他文章

你可能喜欢

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

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

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

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

LikeWater - 1449: 蓝桥杯2014年第五届真题-波动数列C++（动态规划求解）

评论区

精彩推荐

1065

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

点我有惊喜！你懂得！

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

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

程序员的表白（C语言代码）

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

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

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

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

LikeWater

TA的其他文章

你可能喜欢

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

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

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

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

LikeWater - 1449: 蓝桥杯2014年第五届真题-波动数列C++（动态规划求解）

评论区

精彩推荐

1065

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

点我有惊喜！你懂得！

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

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

程序员的表白 （C语言代码）

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

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

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

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

　　评论区

程序员的表白（C语言代码）