牛牛的超市 解题报告

这是一个母函数的题目，其实跟经典的砝码问题没有什么区别。
砝码问题：
假设现在有1克砝码2个，2克砝码1个，4克砝码2个，问能够称出哪些重量，方案数有多少？
解：
可以列出不定方程：
1x1 + 2x2 + 4x3 == r;(0<=x1<=2, 0<=x2<=1, 0<=x3<=2)
所以对应的母函数为：
G(x) = (1+x+x^2) * (1+x^2) * (1+x^4+x^8) = 1+x+2x^2+x^3+2x^4+x^5+2x^6+x^7+2x^8+x^9+2x^10+x^11+x^12
其中 x 的指数就是能够称的重量，而 x 前面的系数就是能够称的重量的方案数；

所以对于这个题来说，就可以看做一个砝码问题，对于样例来说，就可以列出母函数：
G(x) = (1+x+x^2+..+x^5) * (1+x^2+x^4+x^6+x^8)
所以可以解得 x^10 前面的系数为2，即结果为2。
代码：

const int MAXN = 1005;
int ans[MAXN], t[MAXN];
class Solution {
public:
    /**
     * 
     * @param n int整型 ：牛币值种类数
     * @param x int整型 ：牛妹拥有的钱数
     * @param a int整型vector<vector<>> ：第二个vector中的第一列表示币值，第二列表示牛牛拥有币值的个数
     * @return int整型
     */
    int solve(int n, int x, vector<vector<int> >& a) {
        // write code here
        ans[0] = 1;
        for(int i=0; i<n; i++){
            for(int j=0; j<=x; j++) for(int u=0,k=0; u<=a[i][1]&&j+k<=x; u++,k+=a[i][0]) t[j+k] += ans[j];
            for(int j=0; j<=x; j++){
                ans[j] = t[j];
                t[j] = 0;
            }
        }
        return ans[x];
    }
};