妞妞参加了Nowcoder Girl女生编程挑战赛, 但是很遗憾, 她没能得到她最喜欢的黑天鹅水晶项链。
于是妞妞决定自己来制作一条美丽的项链。一条美丽的项链需要满足以下条件:
1、需要使用n种特定的水晶宝珠
2、第i种水晶宝珠的数量不能少于li颗, 也不能多于ri颗
3、一条美丽的项链由m颗宝珠组成
妞妞意识到满足条件的项链种数可能会很多, 所以希望你来帮助她计算一共有多少种制作美丽的项链的方案。
妞妞参加了Nowcoder Girl女生编程挑战赛, 但是很遗憾, 她没能得到她最喜欢的黑天鹅水晶项链。
于是妞妞决定自己来制作一条美丽的项链。一条美丽的项链需要满足以下条件:
1、需要使用n种特定的水晶宝珠
2、第i种水晶宝珠的数量不能少于li颗, 也不能多于ri颗
3、一条美丽的项链由m颗宝珠组成
妞妞意识到满足条件的项链种数可能会很多, 所以希望你来帮助她计算一共有多少种制作美丽的项链的方案。
输入包括n+1行, 第一行包括两个正整数(1 <= n <= 20, 1 <= m <= 100), 表示水晶宝珠的种数和一条美丽的项链需要的水晶宝珠的数量。
接下来的n行, 每行两个整数li, ri(0 <= li <= ri <= 10), 表示第i种宝珠的数量限制区间。
输出一个整数, 表示满足限定条件的方案数。保证答案在64位整数范围内。
3 5 0 3 0 3 0 3
12
对于两种方案,当有任意一种水晶宝珠个数不同,就视为两种不同方案。
#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]]
思路:如果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 |
本套6道题全部pass的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)
#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; }
#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; }
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])
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;
}
}
}
本套试题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;
}
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];
}
}
深度优先超时,改成动态规划了