hdu 2079 选课时间

对于会生成函数（也叫母函数），或者熟悉动态规划的是水题，但对我不是。

花了很久去学习了生成函数，贴一些我觉得还行的资料供没了解过生成函数的人参考

视频：b站 什么是生成函数

两篇博文：略繁琐版，简洁版

我对第二篇博文的第一个例子的代码做了详细注释，也许会有点帮助？hdu 1028

本题代码：

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    int T;
    cin >> T;

    int N, K; // N是最大指数,K是一共有多少个多项式
    while (T--)
    {
        // 初始化
        int ans[43] = {1};
        int cur[43] = {0};
        int poly[10][43] = {0};

        cin >> N >> K;
        int a, b;                    // 学分为a的课有b门
        for (int i = 1; i <= K; i++) // 构造多项式,一共有K种不同学分的课，就等于有K个多项式
        {
            cin >> a >> b;
            for (int j = 0; j <= a * b && j <= N; j += a) // 学分为a的课有b门，那么只有次数为0、a、2a...b*a的项为1，其余为0
            {//还要考虑这门课的学分和数量乘一起 > 所要求的学分， 这种不符题意的情况，所以还要令 j<=N
                poly[i][j] = 1;//第i个多项式的第j项
            }
        }

        for (int i = 1; i <= K; i++) // 一共有K个多项式
        {
            //模拟ans * poly[i]，ans暂时的意思是上一步的乘积结果，算完了才是最后我们要的结果
            //比如1*2*3,ans先存1*2的结果，再去乘3。而下面就是分别用ans的第1、2...项 * 多项式poly[i]
            for (int j = 0; j <= N; j++)
            {
                for (int k = 0; (j + k) <= N; k++)
                {//相乘结果存到对应指数为j+k的项里，比如 2(x^j) * 3(x^k) = 6(x^(j+k))，而cur[j+k]里存的就是系数6，也就是可能的组合数
                    cur[j + k] += ans[j] * poly[i][k]; 
                }
            }

            memcpy(ans, cur, sizeof(cur));
            memset(cur, 0, sizeof(cur));
        }

        cout << ans[N];
        // for (int i = 0; i <= N; i++)
        // {
        // cout<<ans[i];
        // for (int j = 0; j < 41; j++)
        // {
        // cout<<poly[i][j]<<" ";
        // }
        // cout<<endl;
        // }
    }
}