首页 > 试题广场 >

美丽的项链

[编程题]美丽的项链

热度指数：768 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

妞妞参加了Nowcoder Girl女生编程挑战赛, 但是很遗憾, 她没能得到她最喜欢的黑天鹅水晶项链。

于是妞妞决定自己来制作一条美丽的项链。一条美丽的项链需要满足以下条件:

1、需要使用n种特定的水晶宝珠

2、第i种水晶宝珠的数量不能少于l_i颗, 也不能多于r_i颗

3、一条美丽的项链由m颗宝珠组成

妞妞意识到满足条件的项链种数可能会很多, 所以希望你来帮助她计算一共有多少种制作美丽的项链的方案。

输入描述:

输入包括n+1行, 第一行包括两个正整数(1 <= n <= 20, 1 <= m <= 100), 表示水晶宝珠的种数和一条美丽的项链需要的水晶宝珠的数量。
接下来的n行, 每行两个整数l_i, r_i(0 <= l_i <= r_i <= 10), 表示第i种宝珠的数量限制区间。

输出描述:

输出一个整数, 表示满足限定条件的方案数。保证答案在64位整数范围内。

示例1

输入

输出

备注:

对于两种方案，当有任意一种水晶宝珠个数不同，就视为两种不同方案。

算法知识视频讲解

元气の悟空

#include<stdio.h>
#include<string.h>
const int maxn=100;
#define max(a,b) a>b?a:b
int n,m,a[maxn],l[maxn],r[maxn];
long long dp[maxn][maxn+1];
int main(){
    int i,j,k;
    //freopen("input.txt","r",stdin);
    while(~scanf("%d%d",&n,&m)){
        for(i=0;i<n;i++) scanf("%d%d",l+i,r+i);
        memset(dp,0,sizeof(dp));
        for(i=l[0];i<=r[0];i++) dp[0][i]=1;
        for(i=1;i<n;i++)
            for(j=1;j<=m;j++){
                int left=max(0,j-r[i]),right=max(0,j-l[i]);
                for(k=left;k<=right;k++) dp[i][j]+=dp[i-1][k];
            }
        printf("%lld\n",dp[n-1][m]);
    }
}//dp[i][j]表示用前i种宝石组成j颗宝石的项链的方案数
 //但是第i种只能是l[i]到r[i]之间的数量
 //所以dp[i][j]=dp[i-1][j-r[i]]+dp[i-1][j-r[i]+1]+...+dp[i-1][j-l[i]]

发表于 2017-12-30 12:15:00 回复(0)

super3yearsold～

思路：如果n的个数确定可以采用多重循环嵌套，但是由n的个数不确定，思考后可以考虑递归来做，但是递归重复计算次数太多，因而想到可以采用动态规划解决此问题。

设d[i][j]表示i+1种宝珠中取j个宝珠的方案数

k表示宝珠个数上限-宝珠个数下限

则d[i][j]=d[i-1][j]+d[i-1][j-1].....+d[i-1][j-k]

例如：当2种宝珠选2个时的方案数

d[1][2]=d[0][2]+d[0][1]+d[0][0]（选择从第2种宝珠中取i个时的方案数等于从第1种宝珠中分别取2个，取1个，取0个的和）

使用动态规划可得以下二维数组：

	0	1	2	3	4	5
0	1	1	1	1	0	0
1	1	2	3	4	3	2
2	1	3	6	10	12	12

import java.util.Scanner;

public class MeiLiDeXiangLian {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in=new Scanner(System.in);
        int n;
        int m;
        n=in.nextInt();
        m=in.nextInt();
        int l;
        int r;
        int[] array=new int[n];
        for(int i=0;i<n;i++) {
            l=in.nextInt();
            r=in.nextInt();
            array[i]=r-l;
            m=m-l;
        }
        in.close();
        long[][] d=new long[n][m+1];
        for(int i=0;i<=array[0];i++) {//当一种宝珠的取上限个时方案数都为1
            d[0][i]=1;
        }
        for(int i=1;i<n;i++) {
            for(int j=0;j<=m;j++) {
                if(j==0) {
                    d[i][j]=1;
                }else {
                    long sum=0;
                    for(int k=0;k<=array[i]&&k<=j;k++) {
                        sum=sum+d[i-1][j-k];
                    }
                    d[i][j]=sum;
                }
            }
        }
        System.out.println(d[n-1][m]);
    }

}

编辑于 2018-03-23 11:43:48 回复(0)

C/C++

霍七

本套6道题全部pass的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)

牛客网上的其他题目解答也在持续更新。

【题解】为了方便，在输入的时候，将 [li,ri] 的区间缩小为 [0,ri-li] 。

使用动态规划，DP[i][j]为用前i+1种珠宝制作数量为j的项链的方案数量。

DP[i][j+k]=DP[i-1][j]，其中k属于 [0,ri-li]。

#include <iostream>
#include <cstring>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    int *R = new int[n], temp;
    for (int i = 0; i < n; i++) {
        cin >> temp >> R[i];
        R[i] -= temp;
        m -= temp;
    }
    long long int **DP = new long long int*[n];
    for (int i = 0; i < n; i++) {
        DP[i] = new long long int[m + 1];
        memset(DP[i], 0, sizeof(long long int)*(m + 1));
    }
    for (int i = 0; i <= R[0]; i++) {
        DP[0][i] = 1;
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= R[i]; j++) {
            for (int k = 0; k <= m - j; k++) {
                DP[i][k + j] += DP[i - 1][k];
            }
        }
    }
    cout << DP[n - 1][m] << endl;
    delete[] R;
    for (int i = 0; i < n; i++) {
        delete[] DP[i];
    }
    delete[] DP;
    return 0;
}

编辑于 2017-12-26 14:47:29 回复(0)

牛客689560814号

#include<bits/stdc++.h>

usingnamespacestd;

intl[999999],r[999999];

intmain()

{

intn,m;

cin>>n>>m;

for(inti=1;i<=n;i++)

{

cin>>l[i]>>r[i];

}

longlonga[30][200]={0};

a[0][0]=1;

for(inti=1;i<=n;i++)

{

for(intj=0;j<=m;j++)

{

for(intk=l[i];k<=r[i];k++)

{

if(j-k>=0)

{

a[i][j]+=a[i-1][j-k];

}

cout<<a[n][m];

return0;

}

简单！！！！！！！！！！！！！！！！！！！！！！！

发表于 2021-08-31 19:47:42 回复(0)

欧皇👑是个月半球

#include<iostream>
#include<algorithm>
using namespace std;
const int N=30,M=110;
int l[N],r[N];
long long f[N][M];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
    }
    //初始化
    for(int j=l[1];j<=r[1];j++){
        f[1][j]=1;
    }
    //dp
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=l[i];k<=r[i] && k<=j ;k++){
                f[i][j]+=f[i-1][j-k];
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

发表于 2019-12-01 15:40:42 回复(0)

牛客3921511号

n,m=map(int,input().split(' '))
r=[0]*n
l=[0]*n
dp=[[0 for i in range(m+1)] for j in range(n)]
for i in range(n):
    l[i],r[i]=map(int,input().split(' '))
for j in range(l[0],r[0]+1):
    dp[0][j]=1
for i in range(1,n):
    for j in range(1,m+1):
        left=max(0,j-r[i])
        right=max(0,j-l[i])
        for k in range(left,right+1):
            dp[i][j]+=dp[i-1][k]
print(dp[n-1][m])

发表于 2018-05-14 16:13:02 回复(0)

逗比请来的猴子


import java.util.Scanner;

/*
 * 参考大神的解题思路：https://www.nowcoder.com/questionTerminal/e7e0230b12de4239a7f547a01d731522
 *
 * 使用动态规划，dp[i][j]表示从i种宝珠中选取j个的方案数
 * dp[i][j] = dp[i-1][j-k], k可以从第i中宝珠最小数量变化到最大数量
 * */
public class BeatyNeckLace {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            Node[] nodes = new Node[n];
            for (int i = 0; i < n; i++) {
                int start = scanner.nextInt();
                int end = scanner.nextInt();
                nodes[i] = new Node(start, end);
            }
            long[][] dp = new long[n + 1][m + 1];
//            初始化，只有一种宝珠选择的情况
            for (int i = nodes[0].start; i <= nodes[0].end; i++) {
                dp[1][i] = 1;
            }
            for (int i = 2; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
//                    选择该宝珠，可以从最小数量变化到最大数量
                    for (int k = nodes[i - 1].start; k <= nodes[i - 1].end && j - k >= 0; k++) {
                        dp[i][j] += dp[i - 1][j - k];
                    }
                }
            }
            System.out.println(dp[n][m]);
        }
    }

    private static class Node {
        int start, end;

        public Node(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}

发表于 2018-03-27 15:34:30 回复(0)

Reyzal

本套试题AC代码在https://github.com/ReyzalX/nowcoder查看

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    vector<pair<int, int>> range;
    cin >> n >> m;
    range.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> range[i].first >> range[i].second;
    }
    //用i个珠子得到长度为j的手链的方案数
    long long dp[25][105] = {0};
    //只用一种珠子可以得到的方案数
    for (int i = range[0].first; i <= range[0].second; i++)
    {
        dp[1][i] = 1;
    }
    for (int i = 2; i <= n; i++)
    {
        for (int j = i; j <= m; j++)
        {
            //用i颗珠子得到j的方案数
            for (int k = range[i-1].first; k <= j && k <= range[i-1].second; k++)
            {
                dp[i][j] += dp[i-1][j-k];
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

发表于 2018-03-26 01:06:20 回复(0)

alone々孤单

import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int s = scanner.nextInt();
int[][] range = new int[n][2];
for (int i = 0; i < n; i++) {
range[i][0] = scanner.nextInt();
range[i][1] = scanner.nextInt();
}
System.out.println(solution(range,0,s));
}
public static long solution(int[][] range,int pos,int s){
int n = range.length;
long[][] dp = new long[n][s + 1];
for (int i = 0; i < s + 1; i++) {
if(i >= range[n - 1][0] && i <= range[n - 1][1]){
dp[n - 1][i] = 1;
}
}
for (int i = range.length - 2; i >= 0; --i) {
for (int j = 0; j < s + 1; j++) {
//求出范围
int end = j - range[i][0];
int start = j - range[i][1];
start = start > 0 ? start : 0;
for (int k = start; k <= end; k++) {
dp[i][j] += dp[i+1][k];
}
}
}
return dp[0][s];
}
}

深度优先超时，改成动态规划了