【牛客 - 315F】美丽的项链（线性dp，递推，我为人人）

题干：
 

妞妞参加了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位整数范围内。

示例1

输入

复制

3 5 0 3 0 3 0 3

输出

复制

12

备注:

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

解题报告：

  dp[i][j]，代表按顺序用到第 i 种，且用了j颗宝珠  的方法数。

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; ll l[505],r[505]; ll dp[550][550]; int main() {int n,m;cin>>n>>m;for(int i = 1; i<=n; i++) {scanf("%lld%lld",l+i,r+i);} dp[0][0]=1;//通常都这样 for(int i = 1; i<=n; i++) {for(int j = 0; j<=m; j++) {for(int cur,k = l[i]; k<=r[i]; k++) {cur = j+k;dp[i][cur] += dp[i-1][cur-k];}}}printf("%lld\n",dp[n][m]);return 0 ;}

其实可以直接写dp[i][j+k] += dp[i-1][j]，，一种我为人人的想法就完事了。

本来想dp[][][]，，后来发现不行，，想想为什么、、

总结

以上是生活随笔为你收集整理的【牛客 - 315F】美丽的项链（线性dp，递推，我为人人）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。