首页 > 试题广场 >

小Q的歌单

[编程题]小Q的歌单
  • 热度指数：18621 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
小Q有X首长度为A的不同的歌和Y首长度为B的不同的歌，现在小Q想用这些歌组成一个总长度正好为K的歌单，每首歌最多只能在歌单中出现一次，在不考虑歌单内歌曲的先后顺序的情况下，请问有多少种组成歌单的方法。

输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含一个整数，表示歌单的总长度K(1<=K<=1000)。
接下来的一行包含四个正整数，分别表示歌的第一种长度A(A<=10)和数量X(X<=100)以及歌的第二种长度B(B<=10)和数量Y(Y<=100)。保证A不等于B。


输出描述:
输出一个整数,表示组成歌单的方法取模。因为答案可能会很大,输出对1000000007取模的结果。
示例1

输入

5
2 3 3 3

输出

9
算法知识视频讲解
添加回答
civlj头像 civlj

01背包+滚动数组 

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int a,x,b,y,k;
long long dp[1010];
int p[210];
int main() {
    scanf("%d",&k);
    scanf("%d%d%d%d",&a,&x,&b,&y);
    dp[0]=1;
    for(int i=1; i<=x; i++) p[i]=a;
    for(int i=x+1; i<=x+y; i++) p[i]=b;

    for(int i=1; i<=x+y; i++) {
        for(int j=k; j>=p[i]; j--)
            dp[j]=(dp[j]%mod+dp[j-p[i]]%mod)%mod;
    }
    printf("%lld\n",dp[k]%mod);
    return 0;
}
编辑于 2019-01-03 17:16:24 回复(10)
一叶之秋~头像 一叶之秋~
动态规划，模仿背包问题，问题简化为有x+y种物品，其中x种的容积为a，y种的容积为b，背包容积为k，问背包装满一共有多少种解法？
根据题意，只需要用到一维数组即可，代码简单，解法如下： 
import java.util.*;

public class Main{
    public static final int ASD = 1000000007;
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int k=sc.nextInt();
        int a=sc.nextInt(), x=sc.nextInt();
        int b=sc.nextInt(), y=sc.nextInt();
        int[] dp = new int[k+1];
        dp[0] = 1;
        for(int i=0; i<x ; i++){
            for(int j=k; j>=a; j--){
                dp[j] = (dp[j] + dp[j-a]) % ASD;
            }
        }
        
        for(int i=0; i<y ; i++){
            for(int j=k; j>=b; j--){
                dp[j] = (dp[j] + dp[j-b]) % ASD;
            }
        }
        
        System.out.println(dp[k]);
        sc.close();
    }
}

编辑于 2019-02-17 22:11:24 回复(13)
马什么梅呀头像 马什么梅呀
精妙之处就在于如何计算C<m,n>
比如：
205
1 92 4 92
中，可行的解有选92中选13个1、92中选48个4。C<92,48>怎么算？ 
long long c[105][105];
const int mod = 1000000007;
void init()
{
    c[0][0]=1;
    for(int i=1;i<=100;i++){
        c[i][0]=1;
        for(int j=1;j<=100;j++){
            c[i][j] = (c[i-1][j-1]+c[i-1][j])%mod;
        }
    } 
}
利用数学归纳法：
由C(n,k) = C(n-1,k) + C(n-1,k-1）；
对应于杨辉三角：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1 
//小Q的歌单
#include<cstdio>
#include<iostream>
using namespace std;

long long c[105][105];
const int mod = 1000000007;
void init()
{     c[0][0]=1;     for(int i=1;i<=100;i++){         c[i][0]=1;         for(int j=1;j<=100;j++){             c[i][j] = (c[i-1][j-1]+c[i-1][j])%mod;         }     } 
}

int main()
{     int k,i,j,x,y,a,b;     long long sum;     init();     while(cin>>k>>a>>x>>b>>y){         sum = 0;         if(a!=b){             for(i=0;i<=x;i++){                 for(j=0;j<=y;j++){                     if((i*a+j*b)>k)                         break;                     if((i*a+j*b)==k){                         sum+=c[x][i]*c[y][j];                     }                 }             }         }         printf("%ld\n",sum%1000000007);     }     return 0;
 } 

编辑于 2018-07-20 15:21:44 回复(21)
一个更加响亮的名字头像 一个更加响亮的名字
将所有的歌（在例子中就是所有长度为2和长度为3的歌，一共6首）都放入一个数组length[]中，再设置一个二维数组dp[][]，其中dp[ i ][ j ]代表歌曲列表中的前 j 个元素所包含的能够加起来达到长度 i 的组合数（每一个组合所包含歌曲的个数在0 ~ j之间）。

对于dp，当i = 0时，dp[ i ][ j ]也就意味着前j首歌所包含的能够加起来达到长度0 的组合数，这个很显然是1，也就是所有的歌都不添加到和中，因此需要在一开始就把dp[ 0 ][ j ]置为1。     当i > 0， j = 0时，dp[ i ][ j ]的意思就是前0首歌所包含的能够加起来达到长度i 的组合数，这个显然是0，因为0首歌并不能达到 i>0的长度。 若是 j != 0，那么我当前的dp[ i ][ j ]所要考虑的因素有二：第一，前 j 个元素所包含的能够达到长度 i 的组合数，一定大于等于前 j - 1个元素所包含的能够达到长度 i 的组合数（这个很好想到，因为前j-1个元素所包含的所有组合是前j个元素所包含的所有组合的子集）；第二，如果前 j -1 个元素所包含的组合能够到达 （i - length[j]）了，也就意味着只需要在dp[i - length[j]][j - 1]的基础上再添加第j首歌就可以了（length[j]就是第j首歌的长度）。因此：

  如果 length[j] >  i，那么第j首歌一定无法添加到任意组合中去，因为组合出的长度和已经大于 i 了，因此第 j 首歌的加入并不能使得前 j 个元素所包含的满足条件的组合数变多，因此 dp[ i ][ j ] = dp[ i ][ j - 1] ；  

  如果 length[j] = i , 那么第j首歌的加入能够使得前j个元素所包含的满足条件的组合数比前 j - 1首歌所包含的组合数多 1 ，多出来的1就是直接一个第 j首歌的长度刚好够了 i 。

  如果 length[j] < i, 那么第 j 首歌的加入也许能够使得前j 个元素所包含的满足条件的组合数增加，这个取决于 dp[ i - length[ j ] ][ j - 1 ]，如果该值不为0，那么第j首歌加入之后这些组合加上第j首歌的长度刚好达到了i (就是 i - length[ j ] + length[ j ]) ，此时就要把两种情况的组合数相加： dp[ i ][ j ] = dp[ i ][ j - 1]  + dp[ i - length[ j ] ][ j - 1]；  

最后的结果，也就是所有的元素所包含的能够加起来达到长度totalLength的组合数，就是 dp[ totalLength ][ num_A + num_B -1]。

以上某些表述可能有一点点问题，但是动态规划的思路大致描述清楚了。
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int totalLength = sc.nextInt();
        int A = sc.nextInt();
        int num_A = sc.nextInt();
        int B = sc.nextInt();
        int num_B = sc.nextInt();
        int[] lengths = new int[num_A + num_B];
        for (int i = 0; i < num_A; i++) {
            lengths[i] = A;
        }
        for (int i = num_A; i < num_A + num_B; i++) {
            lengths[i] = B;
        }
        int[][] dp = new int[totalLength + 1][num_A + num_B];
        for (int j = 0; j < num_A + num_B; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < totalLength + 1; i++) {
            for (int j = 0; j < num_A + num_B; j++) {
                if (j == 0) {
                    if (lengths[0] == i) dp[i][0] = 1;
                } else {
                    dp[i][j] = dp[i][j - 1] + (lengths[j] <= i ? dp[i - lengths[j]][j - 1] : 0);
                }
            }
        }
        System.out.println(dp[totalLength][num_A + num_B - 1]);
    }
}

发表于 2019-04-04 21:24:36 回复(5)
机智的叉烧头像 机智的叉烧

感觉没那么复杂，分为两块，一块求策略集，另一块求排列组合，组合的公式直接套就行，杨辉三角感觉有点过了。本人渣渣python，C和Java之类的不太会

# coding:utf-8
# 小Q的歌单
def match(a, x, b, y, k):
    get = []
    for i in range(x + 1):
        for j in range(y + 1):
            if i * a + j * b == k:
                get.append([i, j])
    return get
def c(i, j):
    a = 1
    b = 1
    tmp_i = i
    tmp_j = j
    while tmp_i >= 1:
        a = a * tmp_j
        b = b * tmp_i
        tmp_i = tmp_i - 1
        tmp_j = tmp_j - 1
    return a / b
k = int(raw_input().strip())
# print(c(2,4))
[a, x, b, y] = [int(i) for i in raw_input().strip().split()]
get = match(a, x, b, y, k)
if len(get) == 0:
    print 0
else:
    result = 0
    for i in get:
        result = result + c(i[0], x) * c(i[1], y)
    print result % 1000000007
发表于 2018-09-15 10:22:50 回复(7)
lucky_me头像 lucky_me 
//我来解释一下介个吧，自己理解的。
//对于K，如果从X个A中取出i个A之后的差刚好能够除以B，并且（K-A*i）/B结果小于B的个数Y的话，
    // 那么就可以取。结果的个数为：组合C(X,i)*C(Y,（K-A*i）/B)
    //此时算的C就是杨辉三角的计算方法。对于每一行n和每一列m来说，就是从n个中取出m个的组合个数。
public class songListxiaoQ {
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int K = sr.nextInt();
        int A = sr.nextInt();
        int X = sr.nextInt();
        int B = sr.nextInt();
        int Y = sr.nextInt();
        int [][] c = new int[105][105];
        c[0][0] = 1;
        for(int i=1;i<=100;i++)
        {
            c[i][0] = 1;
            for(int j=1;j<=100;j++)
            {
                c[i][j] = (c[i-1][j-1]+c[i-1][j])%1000000007;
            }
        }
        int sum = 0;
        for(int i=0;i<=X;i++)
        {
            if(i*A<=K&&(K-A*i)%B==0&&(K-A*i)/B<=Y)
                sum = (sum+(c[X][i]*c[Y][(K-A*i)/B])%1000000007)%100000007;
        }
        System.out.println(sum);

    }
}
发表于 2018-07-15 21:47:13 回复(5)
woeM头像 woeM 
//dp[i][j]表示总长度为i的歌单，使用前j首歌能组成的总数
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 7;
int main()
{
    int k;
    int lena, x, lenb, y;
    while (cin >> k >> lena >> x >> lenb >> y)
    {
        vector<int> v;
        for (int i = 0; i < x; ++i)
            v.push_back(lena);
        for (int i = 0; i < y; ++i)
            v.push_back(lenb);
        vector<vector<int> > dp(k + 1, vector<int>(x + y, 1));
        for (int i = 1; i < k + 1; ++i)
            if (v[0] != i)
                dp[i][0] = 0;
        for (int i = 1; i < k + 1; ++i)
        {
            for (int j = 1; j < x + y; ++j)
            {
                if (i >= v[j])
                    dp[i][j] = (dp[i][j - 1] + dp[i - v[j]][j - 1]) % mod;
                else
                    dp[i][j] = dp[i][j - 1] % mod;
            }
        }
        cout << dp[k].back() << endl;
    }
}
发表于 2018-05-18 12:36:33 回复(2)
涨涨201907121723662头像 涨涨201907121723662 
k = int(input().strip())
lx, x, ly, y = list(map(int, input().strip().split(" ")))
 
dp = [1] + [0] * k  # 第一位初始化为1
for i in range(x):
    for j in range(k, lx-1, -1):
        dp[j] += dp[j-lx]
         
for i in range(y):
    for j in range(k, ly-1, -ly):  # 第二次步长为ly
        dp[j] += dp[j-ly]
print(dp[k]%1000000007)

编辑于 2019-08-16 13:18:56 回复(2)
Java
newch头像 newch 
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int length = scan.nextInt();
        int A = scan.nextInt();
        int X = scan.nextInt();
        int B = scan.nextInt();
        int Y = scan.nextInt();
        System.out.println(qlist(length, A, X, B, Y));
    }

    public static long qlist(int length, int A, int X, int B, int Y) {
        long mod = 1000000007;
        // 构建杨辉三角
        int max = 101;
        long[][] tri = new long[max][max];
        tri[0][0] = 1;
        for (int i = 1; i < max; i++) {
            tri[i][0] = 1;
            for (int j = 1; j < max; j++) {
                tri[i][j] = (tri[i - 1][j - 1] + tri[i - 1][j]) % mod;
            }
        }
        long sum = 0;
        for (int value = 0; value <= length; value++) {
            if (value % A == 0 && (length - value) % B == 0 && value/A <= 100 && (length - value) / B <= 100) {
                sum += tri[X][value / A] * tri[Y][(length - value) / B] % mod;
            }
        }
        return sum % mod;
    }
}
杨辉三角 ac
编辑于 2018-07-23 21:57:12 回复(0)
牛客3921511号头像 牛客3921511号
暴力搜索可能的组合方式，再用排列组合求出总的可能数 
K=int(raw_input())
a,na,b,nb=map(int,raw_input().strip().split(' '))
arr=[a for i in range(na)]
brr=[b for j in range(nb)]
M=1000000007
def get_value(n):  
    if n==1:  
        return n  
    else:  
        return n * get_value(n-1)  
def gen_last_value(n,m):  
    first = get_value(n)  
     
    second = get_value(m)  
     
    third = get_value((n-m)) if n!=m else 1  
     
    return first/(second * third) if n!=m else 1
ans=0
for i in range(na+1):
    for j in range(nb+1):
        
        if a*i+b*j==K:
            if i!=0 and j!=0:
                ans+=gen_last_value(na,i)*gen_last_value(nb,j)
            elif i==0 and j==0:
                ans+=0
            else: 
                ans+=gen_last_value(na,i) if i!=0 else gen_last_value(nb,j)
print int(ans%M)  

发表于 2018-05-18 12:44:02 回复(0)
Xeon92头像 Xeon92
求解x*A+y*B=K，其中0<=x<=X, 0<=y<=Y，总方法数为所有解(x,y)的C(X,x)*C(Y,y)之和。另外注意组合数溢出。

编辑于 2018-07-25 17:35:05 回复(0)
pyxiea头像 pyxiea
遇到了一道可秒杀的模板题。。。这就是01背包的求解方案数的模板题，如果想查看类题以及思路解析，可以见这篇博客：https://blog.csdn.net/xpy870663266/article/details/103197578 

import sys
 
 
def parse_nums(nums_str):
    return [int(x) for x in nums_str.strip().split()]
 
 
# 基本输入输出
for s in sys.stdin:
    s = int(s)
    v1, n1, v2, n2 = parse_nums(input())
    v = [v1] * n1 + [v2] * n2
    n = n1 + n2
    dp = [0] * (s + 1)
    dp[0] = 1
    for i in range(n):
        for j in range(s, v[i] - 1, -1):
            dp[j] = (dp[j] + dp[j - v[i]]) % 1000000007
    print(dp[s])


编辑于 2020-03-30 11:45:16 回复(2)
zzmim头像 zzmim 
#include<iostream>
using namespace std;
 
#define mod 1000000007
long long  arr[105][105];
 
void cal_c(){
    arr[0][0] = 1;
    for(int i = 1; i <= 100; ++i){
        arr[i][0] = 1; 
        for(int j = 1; j <= i; ++j)
            arr[i][j] = (arr[i-1][j] + arr[i-1][j-1]) % mod;
    }
}
 
int main(){
    int k,a,x,b,y;
    long long ret = 0;
    cin>>k>>a>>x>>b>>y;
    cal_c();
    for(int i = 0; i <= x; ++i)
        for(int j = 0; j <= y; ++j){
            if(a*i+b*j > k) break;
            else if(a*i+b*j == k) ret = (ret + arr[x][i] * arr[y][j]) % mod;
        }
    cout<<ret;
    return 0;
}

发表于 2019-12-05 13:15:50 回复(0)
Python
Mrs.Jing头像 Mrs.Jing 
# 组合数 C^(a)_(b)
def cnn(a,b):
    if a == 0:
        return 1
    fz,fm = 1,1
    for i in range(a):
        fz *= (b-i)
    for i in range(a):
        fm *= (i+1)
    return fz//fm

K = [int(x) for x in input().split()][0]
A,X,B,Y = [int(x) for x in input().split()]

# 组合方式, 即求解策略集
zhfs = []
a_max = min(K//A, X)
b_max = min(K//B, Y)
for a in range(a_max+1):
    b = 0
    while a*A + b*B <= K and b <= b_max:
        if a*A + b*B == K:
            zhfs.append([a, b])
        b += 1


ans = 0
if not zhfs:
    print(0)
else:
    for i,j in zhfs:
        ans += (cnn(i,X)*cnn(j,Y))
    print(ans%1000000007)
python 3代码，本人计算机渣的一批，确实没看出来题目和杨辉三角的关系。。
编辑于 2019-08-17 15:58:36 回复(0)
Python
管子_no1头像 管子_no1

python3

  • 说实话对当前我来说挺难
    # 动态规划，模仿背包问题，问题简化为有x+y种物品，其中x种的容积为a，y种的容积为b，背包容积为k，问背包装满一共有多少种解法？
# dp[i][j]: i 代表背包容积, j 代表前 j 个物品, 前 j 个元素恰填满容积为 i 的背包的组合数
k = int(input())
num_list = list(map(int, input().split()))
a, x, b, y = num_list[0], num_list[1], num_list[2], num_list[3]
things = [0] + [a for i in range(x)] + [b for i in range(y)] # 长度为 a+b+1
dp = [[0 for j in range(x+y+1)] for i in range(k+1)]
for i in range(x+y+1):
  dp[0][i] = 1
# 考虑 i > 0
for i in range(1, k+1):
  for j in range(1, x+y+1):
      if things[j] > i:
          dp[i][j] = dp[i][j-1]
      elif things[j] == i:
          dp[i][j] = dp[i][j-1] + 1
      elif things[j] < i:
          if dp[i-things[j]][j-1] != 0: #
              dp[i][j] = dp[i][j-1] + dp[i-things[j]][j-1]
          else:
              dp[i][j] = dp[i][j-1]
print(int(dp[k][x+y])%1000000007)
发表于 2019-08-16 16:18:39 回复(0)
Python
牛客用户568435头像 牛客用户568435 

	import sys





	if __name__ == "__main__":





	    data=[]





	while True:





	    line = sys.stdin.readline().strip()





	    if not line:





	        break





	    tmp = list(map(int, line.split(" ")))





	    data.append(tmp)





	n=data[0][0]





	l=data[1]





	length=[0]





	for i in range(l[1]):





	    length.append(l[0])





	for i in range(l[-1]):





	    length.append(l[-2])





	def gedan(n,length):





	    dp=[[0 for i in range(len(length))]for i in range(n+1)]





	    for i in range(5):





	        dp[0][i]=1





	    for j in range(1,n+1):





	        dp[j][0]=0





	    for i in range(1,n+1):       





	        for j in range(1,len(length)):





	            if length[j] > i:





	                dp[i][j] = dp[i][j-1]





	            elif length[j] == i:





	                dp[i][j]=dp[i][j-1]+1





	            else:





	                dp[i][j] = dp[i][j-1]+dp[i-length[j]][j-1]               





	    return dp[n][len(length)-1]%1000000007





	print(gedan(n,length))

发表于 2019-06-12 16:40:29 回复(1)
Python
东不拉头像 东不拉 
'''    import itertools  K = int(input()) A,X,B,Y = input().split() A,X,B,Y = int(A), int(X), int(B), int(Y)  result = 0  list_X = list(range(X)) list_Y = list(range(Y)) for x in range(X+1):  for y in range(Y+1):  k = A * x + B * y  if k == K:  print("%d = %d * %d + %d * %d"%(k, A, x, B, y))  result_X = list(itertools.combinations(list_X, x))  result_Y = list(itertools.combinations(list_Y, y))  print(result_X)  print(result_Y)  result += len(result_X) * len(result_Y) result = result % 1000000007 print(result) '''  import math def C(n,m):
    m1 = m
    m2 = m
    uper = 1  downer = 1  while(m1>0):
        uper *= n
        m1 -= 1  n -= 1   while(m2>0):
        downer *= m2
        m2 -= 1  return int(uper/downer)
K = int(input())
A, X, B, Y = map(int, input().strip().split(' '))
result = 0 for x in range(X+1): for y in range(Y+1):
        k = A * x + B * y if k == K: print(x,y)
            result += C(X,x) * C(Y,y)
result = result % 1000000007 print(result)





链接：https://www.nowcoder.com/questionTerminal/f3ab6fe72af34b71a2fd1d83304cbbb3

来源：牛客网

您的代码已保存

答案错误:您提交的程序没有通过所有的测试用例

case通过率为70.00%

测试用例:

205

1 92 4 92

对应输出应该为:

580636981

你的输出为:

162025174



这是什么原因？

发表于 2018-09-16 13:01:46 回复(7)
浅歌一梦头像 浅歌一梦
//找到K值得组成方法，再累加
var k = parseInt(readline());
var readArr = readline().split(" ");
var num1 = parseInt(readArr[0]),count1 = parseInt(readArr[1]),
num2 = parseInt(readArr[2]),count2 = parseInt(readArr[3]);
var temp;
function CXY(x,y){
var sum=1;
var temp = x;
if(y==0) return sum;
for(var i =1;i<=Math.min(y,x-y);i++){
sum=sum*temp/i;
temp--;
}
return sum;
}
//num1和count1存放个数少的一组数（歌长，歌数）
if(count1>count2){
temp = count1;
count1 = count2;
count2 = temp;
temp = num1;
num1 = num2;
num2 = temp;
}
var sum = 0;
for(var i=0;i<=count1;i++){
if((k-num1*i)>0 && (k-num1*i)%num2==0 && (k-num1*i)/num2<=count2){
sum+=CXY(count1,i)*CXY(count2,(k-num1*i)/num2);
}
} 
print(sum%1000000007)

编辑于 2018-08-29 18:10:01 回复(1)
Java
InseQM头像 InseQM 
 public class SongSheetForQ {
    public static long[][] arr = new long[101][101];
    public static long constituteMethod(int K, int A, int X, int B, int Y){
        long result = 0;
        int length;
        arr[0][0] = 1;
        for (int i = 1; i <= 100; i++){
            arr[i][0] = 1;
            for (int j = 1; j <= 100; j++) {
                arr[i][j] = (arr[i - 1][j] + arr[i - 1][j - 1]) % 1000000007;
            }
        }
        for (int i = 0; i <= X; i++){
            length = K - A * i;
            if (length >= 0 && length % B == 0 && length / B <= Y){
                result += (arr[X][i] * arr[Y][length / B]);
            }
        }
        return result % 1000000007;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        int A = sc.nextInt();
        int X = sc.nextInt();
        int B = sc.nextInt();
        int Y = sc.nextInt();
        sc.close();
        System.out.println(constituteMethod(K, A, X, B, Y));
    }
}
发表于 2018-07-20 17:10:03 回复(0)
想提桶的打工鸭头像 想提桶的打工鸭 
#include<iostream>
#include<stdlib.h>
#include <math.h>
using namespace std;
const int mod=1000000007;
int main()
{
    int i, j, K, la, lb, na, nb,result;
    cin >> K;
    cin >> la >> na >> lb >> nb;             //输入的信息
    int *lens=new int[na+nb+1];            //建立动态数组lens[j]表达第j首歌长度
    for(i=1;i<=na;i++){                    
        lens[i]=la;
    }
    for(i=1;i<=nb;i++){
        lens[i+na]=lb;
    }                                    //将na,nb数量的歌的长度按顺序存储进数组lens
    
    int **db=new int*[K+1];        //建立二维动态数组db[i][j]存储j首歌组成长度为i的方法
    for(int i=0;i<K+1;i++){
        db[i]=new int[na+nb+1];
    }                               //为二维数组申请内存
    for(int j=1;j<na+nb+1;j++){
        db[0][j]=1;
    }                              //所有j首歌组成长度为0的方法为1
    for(int i=1;i<K+1;i++){
        if(lens[1]!=i){
            db[i][1]=0;
        }
        else
            db[i][1]=1;
    }                          //用1首歌组成长度为i的方法根据长度判断
    for(i=1;i<K+1;i++){
        for(j=2;j<na+nb+1;j++){
            if(i>=lens[j])
                db[i][j]=(db[i][j-1]+db[i-lens[j]][j-1])%mod;
        else            db[i][j]=db[i][j-1]%mod;
    }
    }
   //当i的长度大于等于第j首歌长度时,用j首歌组成长度为i的方法分两部分,1部分为用j-1首歌组成长度为i的歌单
   //另一部分为由j-1首歌组成长度为i-lens[j]的歌单,因为第j首歌长度恰好为lens[j]
    cout<<db[K][na+nb]<<endl;       //输出最后由na+nb首歌组成长度为K的歌单的方法总数

    system("pause");
    return 0;
}

发表于 2018-07-19 15:36:05 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 腾讯 动态规划 2018 Java工程师
上传者：小小
难度：
58条回答 24508浏览

热门推荐

通过挑战的用户

相关试题

小Q的歌单

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号