LikeWater

用户名：dotcpp0632461

访问量：6950

签　名：

KaMi

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

　　自我简介：

TA的其他文章

LikeWater - 1097: 蛇行矩阵
浏览：26

LikeWater - 2701: 蓝桥杯真题-取模（请问有谁知道看错题的痛！一直看成n mod x == m mod y 隔这儿一只写。。。）
浏览：298

你可能喜欢

A+B for Input-Output Practice (VII) （C语言代码）

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

　　作者: LikeWater　　　　发表时间：2023-03-09 21:44:39 浏览：329　|　评论：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分

7 人评分

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

　　评论区

LikeWater

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

2023-03-09 21:45:13

LikeWater

TA的其他文章

你可能喜欢

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

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

A+B for Input-Output Practice (VII) （C语言代码）

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

矩阵转置（C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）for循环

最小公倍数（C语言代码）

WU-蓝桥杯算法提高VIP-企业奖金发放（C++代码）

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

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

【蟠桃记】（C语言代码）

幸运数（C++代码）

1054题解

DNA （C语言代码）

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

LikeWater

TA的其他文章

你可能喜欢

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

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

A+B for Input-Output Practice (VII) （C语言代码）

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

矩阵转置 （C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）for循环

最小公倍数 （C语言代码）

WU-蓝桥杯算法提高VIP-企业奖金发放 （C++代码）

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

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

【蟠桃记】 （C语言代码）

幸运数 （C++代码）

1054题解

DNA （C语言代码）

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

矩阵转置（C语言代码）

　　评论区

最小公倍数（C语言代码）

WU-蓝桥杯算法提高VIP-企业奖金发放（C++代码）

【蟠桃记】（C语言代码）

幸运数（C++代码）

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