HDU-2079-选课时间-多重背包

「爱情、让人受尽委屈。」 2022-05-27 03:14 121阅读 0赞

# 选课时间(题目已修改,注意读题)          #

### 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<bits/stdc++.h>///选课时间(题目已修改,注意读题)
    using namespace std;
    int f[50];
    int main()
    {
        int t,n,k,a,b;
        scanf("%d",&t);
        while(t--)
        {
            memset(f,0,sizeof(f));
            f[0]=1;
            scanf("%d%d",&n,&k);
            for(int i=0;i<k;i++)
            {
                scanf("%d%d",&a,&b);
                for(int j=n;j>=a;j--)
                {
                    for(int l=1;l<=b;l++)
                    {
                        if(j>=l*a)f[j]=f[j]+f[j-l*a];
                    }
                }
            }
            printf("%d\n",f[n]);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，121人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 2844-Coins(多重背包)

Coins Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others

我就是我/ 2022年07月24日 08:14/ 0 赞/ 166 阅读

相关 HDU 2079 选课时间(题目已修改,注意读题) [母函数]

选课时间(题目已修改,注意读题) Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768

雨点打透心脏的1/2处/ 2022年05月30日 12:44/ 0 赞/ 142 阅读

相关 HDU-1059 Dividing（多重背包）

Dividing Problem Description Marsha and Bill own a collection of marbles. T

古城微笑少年丶/ 2022年05月30日 05:18/ 0 赞/ 147 阅读

相关 HDU 1171 Big Event in HDU [多重背包]

include <stdio.h> include <string.h> include <math.h> include <algorithm

分手后的思念是犯贱/ 2022年05月29日 10:24/ 0 赞/ 155 阅读

相关 hdu 2079 - 选课时间

地址 [http://acm.hdu.edu.cn/showproblem.php?pid=2079][http_acm.hdu.edu.cn_showproblem.p

野性酷女/ 2022年05月28日 13:27/ 0 赞/ 137 阅读

相关 HDU-2079-选课时间-多重背包

选课时间(题目已修改,注意读题) Problem Description 又到了选课的时间了，xhd看着选课表发呆，为了想让下一学期好过点，他想知

「爱情、让人受尽委屈。」/ 2022年05月27日 03:14/ 0 赞/ 122 阅读

相关 HDU 2079 选课时间

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) To

青旅半醒/ 2022年05月09日 12:26/ 0 赞/ 151 阅读

相关 HDU 2844 Coins(多重背包)

HDU 2844 Coins(多重背包) [http://acm.hdu.edu.cn/showproblem.php?pid=2844][http_acm.hdu.e

刺骨的言语ヽ痛彻心扉/ 2022年03月31日 10:35/ 0 赞/ 172 阅读

相关【HDU 1059】Dividing（多重背包）

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1059][http_acm.hdu.edu.cn_showproblem.ph

落日映苍穹つ/ 2022年03月09日 00:09/ 0 赞/ 169 阅读

相关多重背包

n个物品，每个可以取k次，容量为w，价值为v。一般做法：二进制拆分：将每个物品拆成O(log k)个01背包的物品，时间复杂度为(nmlogk) 例如：K=10 可以拆分

矫情吗；*/ 2021年12月23日 11:05/ 0 赞/ 326 阅读