http://acm.hdu.edu.cn/showproblem.php?pid=2079
Problem Description
又到了选课的时间了,xhd看着选课表发呆,为了想让下一学期好过点,他想知道学n个学分共有多少组合。你来帮帮他吧。(xhd认为一样学分的课没区别)
Input
输入数据的第一行是一个数据T,表示有T组数据。
每组数据的第一行是两个整数n(1 <= n <= 40),k(1 <= k <= 8 )。
接着有k行,每行有两个整数a(1 <= a <= 8 ),b(1 <= b <= 10),表示学分为a的课有b门。
Output
对于每组输入数据,输出一个整数,表示学n个学分的组合数。
Sample Input
2
2 2
1 2
2 1
40 8
1 1
2 2
3 2
4 2
5 8
6 9
7 6
8 8
Sample Output
2
445
#include <iostream>
using namespace std;
int dp[650], temp[650], M, num[10], w[10];
void gfun (int cost, int amount)
{
int j, x;
for (j = 0; j <= M; j++) //枚举构造对象
for (x = 0; j - x * cost >= 0 && x <= amount; x++) //枚举物品数
temp[j] += dp[j-x*cost]; //可以用递推的思想去理解
for (j = 0; j <= M; j++) //滚动数组
{
dp[j] = temp[j];
//cout << dp[j] << ' ';
temp[j] = 0;
}
//cout << endl;
}
int main()
{
int i, n, t;
scanf ("%d", &t);
while (t--)
{
memset (temp, 0, sizeof(temp));
memset (dp, 0, sizeof(dp));
dp[0] = 1;
scanf ("%d%d", &M, &n);
for (i = 0; i < n; i++)
{
scanf ("%d%d", w+i, num+i);
gfun (w[i], num[i]);
}
printf ("%d\n", dp[M]);
}
return 0;
}
分享到:
相关推荐
【标题】"hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084" 提供的是一个关于杭电(HDU)ACM竞赛第1084题的解决方案。该题目可能是在编程竞赛中常见的算法问题,而ACM(国际大学生程序设计竞赛)是全球知名的编程...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
杭电hdu acm资料所用杭电的acm题
hdu_2102_passed_sorce
【描述】"HDU一部分题目原码,大部分是可运行的,可能有几题不完整" 表明这个压缩包中的内容主要是HDU平台上一些编程题目的解决方案,源代码文件。这些代码大部分是可以直接运行的,意味着它们已经实现了题目所要求...
HDU_ACM培训课件是面向参与ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC)的学员准备的一套完整的教程资源。这个压缩包包含了丰富的学习资料,旨在帮助参赛者提升编程技能...
"HDU Page 11 Answer"提供的题解资源,不仅节省了逐一搜索题解的时间,还提供了一次性获取多题答案的机会。通过对比不同解法,学习者可以开阔思路,理解多种解决问题的角度,进一步提升编程素养。 总之,"HDU Page ...
HDU_ACM_1002_大数相加C源代码,利用字符串处理
这份名为"HDU.rar"的压缩包文件,包含了针对杭电(Hangzhou Dianzi University,简称HDU)ACM竞赛平台上的2000至2099号题目的一系列解题报告。这些报告以".chm"(Compiled Help Manual)格式存储,是专门为ACM(国际...
这道题目来源于HDU(杭州电子科技大学)的在线判题系统,通常这类题目是编程竞赛或者算法训练的一部分。"Rightmost Digit"直译为“最右边的数字”,我们可以推测这是一个关于数字处理的问题,可能涉及到对整数的数学...
杭电期中期末复习资料档案库_HDU_QuickLearner
【标题】"HDU_软工_计组实验1~8"所涵盖的知识点主要集中在计算机组织(简称计组)的实践操作层面,这通常包括对计算机硬件结构、指令系统、存储器体系、数据表示以及处理器工作原理等基础知识的深入理解和应用。...
在本压缩包文件“模式识别_hdu_期末复习资料集合_试卷笔记.zip”中,我们可以期待找到与杭州电子科技大学(HDU)模式识别课程相关的期末复习资料,可能包括过去的试卷、笔记和其他学习材料。 模式识别的基本概念...
【标题】"sanguosha.rar_hdu_三国杀_标程" 提供的是一个关于 HDU(杭州电子科技大学在线判题系统)3378 题目的解题报告,该题目名为“三国杀”,并且包含了一份用 C++ 编写的程序代码“san guo sha.cpp”。...
标题中的“DP.rar”表明这是一个关于动态规划的资料压缩包,而“DP_hdu”暗示了这些题目可能来自杭州电子科技大学(HDU)的在线编程平台。动态规划通常用于解决那些可以通过子问题的最优解来构建原问题最优解的问题...
B_(HDU_1231)(最大子段和,分治).cpp
这个压缩文件包含的是作者个人提交并解决的ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)题目,这些题目来源于HDU的在线编程平台。 【描述】"杭电的一些acm题目,都是我自己一个一...
题目链接题目意思给你n个点,让你在这n个点之间加边,但是不管咋加都不能形成三个点的直接相通环,让求最大的边数。要求最大的边数还不能出现三个边的环,我们可以将n个
这个压缩包“数字图像处理_hdu_期末复习资料_试卷等.zip”显然是为杭州电子科技大学(HDU)的学生准备的期末复习材料,包含了一些关于这门课程的试卷。下面,我们将详细探讨数字图像处理的一些核心知识点。 1. 图像...