波动数列,简易AC代码,详细讲解。

波动数列

题目描述
观察这个数列:

1 3 0 2 -1 1 -2 …

这个数列中后一项总是比前一项增加2或者减少3,且每一项都为整数。

栋栋对这种数列很好奇,他想知道长度为 n 和为 s 而且后一项总是比前一项增加 a 或者减少 b 的整数数列可能有多少种呢?

输入格式
共一行,包含四个整数 n,s,a,b,含义如前面所述。

输出格式
共一行,包含一个整数,表示满足条件的方案数。

由于这个数很大,请输出方案数除以 100000007 的余数。

这道题真的是需要自己花时间来理解细节。
不过请相信,付出一定会有收获,只要攻下这道坎,相信一定能得到提升!

思路:

如下图所示,该序列的首项是x,公差为set,set={a,-b};

通过下边的第一幅图我们可以知道,set的数量为n*(n-1)/2 (公式:首项加末项除以2)

我们令cnt=n*(n-1)/2 (也就是set的数量) 通过这些分析我们可以知道满足这么一个条件:序列总和=Sn=nx+cntset

我们假设a的数量为num1,因为a,b数量的总和是cnt,则b的数量就是cnt-num1; 可推出一个表达式nx+a * num1-b(cnt-num1)=s;转换一下位置也就是n * x=s-anum1+b(cnt-num1);。我们上边已经说了set的最大数量为n(n-1)/2,set有a和b两种可能,假若全是a,也就是最多有n*(n-1)/2个a(此时0个b),知道这个公式后就好办了因为公式里只有两个未知数x和num1,并且我们说了num1(也就是a的数量)上限是n*(n-1)/2 ,我们只需要通过枚举对这n*(n-1)/2 进行一次for循环,找出满足条件的值即可,知道了满足条件的num1后自然也就知道了x的值。讲到这里后,我们介绍一下下边这段代码,我直接把注释打在代码中。

    int ans=0;//用来记录满足条件的次数。
	int cnt=n*(n-1)/2;		//a和b数量的总和。
    for(int i=0;i<=cnt;i++)	//这里其实就是在从0开始枚举a的所有可能的数量,只要满足x是个整数,则说明此时这个数量的a是符合条件的。
    {
        long long h=s-i*a+(cnt-i)*b;
        //首先需要知道这段代码的意思,结合上边的公式可以知道这里的h代表的就算n*x; 这也就是为什么会有下边if判断的原因
        if(h%n==0)//这个判断的意思也就是想表达,只要求出的x是一个整数,那么此时的a的数量就是满足条件的。
            ans+=f[i];//这里的f[i]我会在下边介绍,反正只需要知道此时这个for循环中i的数量就是a的数量,f[i]则表明当前数量的a满足的组合,可能大家看到这里看不懂我说的是什么组合了,我会在下边介绍
    }
序号 对应值
0 x
1 x+set
2 x+set+set
n-1 x+(n-1)*set

情况1:

序号 对应值
1 x
2 x+a
3 x+a-b
4 x+a-b+a
5 x+a-b+a+a
总和 5x+7a-3b

a的数量是7,是由4+2+1组成的7

情况2:

序号 对应值
1 x
2 x+a
3 x+a+a
4 x+a+a-b
5 x+a+a-b-b
总和 5x+7a-3b

a的数量是7,却是由4+3组成的,对应的b的数量为3,是由2+1组成的。

大家请看这两种情况,虽然都是7个a,但是不是他们有不同的排列的可能,最重要的细节就在这里了,尽管我们通过那边那个步骤能够求出a的数量,但是a的组合方式还不知道,所有问题转变到求a的组合方式的可能性,上代码。

#include <iostream>
using namespace std;
long long n,s,a,b;
int f[100];//它的下标是a的个数,假设a=7,f[7]就代表当a个数是7的时候,可以有多少种可能来组成这个数字。可以是4+3,也可以是4+2+1,就像上边介绍的那两种情况一样。

//再讲下边这个函数的实现的时候,可能有同学会看不懂,它跟01背包问题的思路很相似,都用到了滑动数组的思想,可以看一下我上边对01背包问题的讲解,如果掌握了,相信对你的编程能力会有一定的帮助。

//下边这个动态规划是直接将二维的思想转化成一维来实现的。如果有不懂的可以去看下我01背包问题的讲解。
//我们先模拟用二维的方式来进行讲解。就用二维数组f[i][j]吧,下边的这种方式是直接将二维数组f[][]转化成了一维数组f[]。
//在正式开始讲前,以防大家混淆了二维数组f[][]的作用,这里说明一下,它跟求a的数量没有任何关系,是在a的数量求出来后,通过这个数组来分析a的数量个数可以有哪些组合方式,比如上边说到的当a个数是7的时候,可以有多少种可能来组成这个数字。可以是4+3,也可以是4+2+1。
//好了,接着正式说明f[i][j]中i和j代表的含义,i代表的是当前a的可能数,一定记得只是a,跟b没关系(可以是1,2,3,4...),它是从1开始的,j代表的是前i个数的数值总和。
//首先说明一点f[i][0]的值都必须先设为1。这里很细节,下边我举几个例子就明白了。
//   f[i][j]=f[i-1][j]  ,这是当j<i的时候。
//	f[i][j]=f[i-1][j]+f[i-1][j-i],这是当j>=2的时候。
//我再跟大家细致的讲解一下i的真正含义,比如说f[3][2],它的意思就是在数字1,2,3中挑任意数组能组成最终和(j),这里对应的就和(j)就是2,能组成2,只有一种情况就是直接选2出来,所有f[3][2]=1(此时请注意f[3][2]中是j<i的情况,用的公式是f[i][j]=f[i-1][j]。在举例,比如f[4][2],意思就是在1,2,3,4这四个数字中选任意数字来得到2,只有一种可能,即是直接选2,所以f[4][2]=1,(此时请注意f[4][2]中是j<i的情况,用的公式是f[i][j]=f[i-1][j]。而f[3][3],代表的意思是从1,2,3这三个数字中选任意数字能组成和(j),这里对应的和(j)就是3,要组成3,有两种方式,选1和2,或者直接选3,所以f[3][3]=2,(此时请注意f[3][3]中是j>=i的情况,所以用的公式是f[i][j]=f[i-1][j]+f[i-1][j-i]),我们带入具体数字进去就是f[3][3]=f[2][3]+f[2][0],请注意看这里是不是出现了f[3][0],也就是上边说到的f[i][0]的情况,这也就是为什么要把f[i][0]都设置为1,因为此时j=i,所以出现了f[2][0],我们深度刨析一下f[3][3]=f[2][3]+f[2][0]的意思,左边部分f[3][3]需要在右边部分(也就是上一次的状态上)进行叠加计算,这句表达式的f[2][3]代表要在1,2这两个数字中找到能组合出3的情况,就是1+2,也就是1,2两个数字都要选。而f[2][0]这部分的意思则是此时左边已经是f[3][3],从原来的1,2两个数中选,变到了现在的从1,2,3中选,并且选出了3(重点理解),所以f[2][0]的作用是判断,已经选了3后(重点理解),再从1,2这两个数字中选出满足0的情况,这也解释了为什么要把所有的f[i][0]都设置为1。    好了我只能讲到这个程度了,至于下边的如何将二维f[i][j]转化为一维f[i]请参考我讲到的01背包问题,强烈建议大家看懂这两道题,对你理解动态规划有很大的帮助!!
void dp(int x)		
{
    f[0]=1;
    for(int i=1;i<x;i++)	//简单说一下为什么是i<x,而不是i<=x,请看下表,a是从序号2才开始出现的,自己好好理解一下。

//| 序号 | 对应值    |
//| :--: | :-------- |
//|  1   | x         |
//|  2   | x+a       |
//|  3   | x+a+a     |
//|  4   | x+a+a-b   |
//|  5   | x+a+a-b-b |
//| 总和 | 5x+7a-3b  |
    {
        for(int j=i*(1+i)/2;j>=i;j--)
        {
            f[j]=f[j]+f[j-i];
        }
    }
}

完整代码:

#include <iostream>
using namespace std;
long long n,s,a,b;
int f[100];
void dp(int x)		
{
    f[0]=1;
    for(int i=1;i<x;i++)
    {
        for(int j=i*(1+i)/2;j>=i;j--)
        {
            f[j]=f[j]+f[j-i];
        }
    }
}
int main()
{
   cin>>n>>s>>a>>b;
    dp[n];
    int ans=0;
    int num=n*(n-1)/2;
    for(int i=0;i<=num;i++)
    {
        long long h=s-i*a+(num-i)*b;
        if(h%n==0)
            ans+=f[i];
    }
    cout<<ans;
    system("pause");
    return 0;
}
上一篇:Redis基本操作---------string类型


下一篇:ES6模块化遇到的跨源问题Access to script at ‘X.js‘ from origin ‘null‘ has been blocked by CORS policy... 解决方法