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

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4478 Accepted Submission(s): 3480

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

1 2

2 1

40 8

1 1

2 2

3 2

4 2

5 8

6 9

7 6

8 8

Sample Output

445

最开始用多重背包做，发现二进制优化多出的零头可能发生重复，但是没相处解决方案。

看题解用的01背包，稍作修改避免了重复。

因为数据规模小，用dfs也很方便。

01背包：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int cost[],num[],dp[],n;

void zero_one(int cost,int num)

{

    for(int j=n;j>=cost;j--)

        for(int k=;k<=num&&j-k*cost>=;k++)

            dp[j]+=dp[j-cost*k];

}

int main()

{

    int t,k;

    scanf("%d",&t);

    while(t--)

    {

        memset(dp,,sizeof(dp));

        dp[]=;

        scanf("%d%d",&n,&k);

        for(int i=;i<k;i++)

        {

            scanf("%d%d",&cost[i],&num[i]);

            if(cost[i]*num[i]>n)

                num[i]=n/cost[i];

            //dp[cost[i]]=1;

        }

        for(int i=;i<k;i++)

        {

            zero_one(cost[i],num[i]);

        }

        printf("%d\n",dp[n]);

    }

    return ;

}

dfs：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int cost[],num[],res,n,k;

void dfs(int index,int sum)

{

    if(index>k||sum>n)

        return;

    if(index==k&&sum!=n)

        return;

    if(sum==n)

    {

        res++;

        return;

    }

    for(int i=;i<=num[index];i++)

    {

        dfs(index+,sum+i*cost[index]);

    }

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        res=;

        scanf("%d%d",&n,&k);

        for(int i=;i<k;i++)

            scanf("%d%d",&cost[i],&num[i]);

        dfs(,);

        printf("%d\n",res);

    }

    return ;

}

巴特西

HDU_2079_(01背包)(dfs)

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

最新文章

热门文章