HDU1248 寒冰王座(母函数)

秒速五厘米 2022-06-09 11:07 170阅读 0赞

## 寒冰王座 ##

不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.

死亡骑士:”我要买道具!”

地精商人:”我们这里有三种道具,血瓶150块一个,魔法药200块一个,无敌药水350块一个.”

死亡骑士:”好的,给我一个血瓶.”

说完他掏出那张N元的大钞递给地精商人.

地精商人:”我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿.”

死亡骑士:”……”

死亡骑士想,与其把钱当小费送个他还不如自己多买一点道具,反正以后都要买的,早点买了放在家里也好,但是要尽量少让他赚小费.

现在死亡骑士希望你能帮他计算一下,最少他要给地精商人多少小费.  
**Input**  
输入数据的第一行是一个整数T(1<=T<=100),代表测试数据的数量.然后是T行测试数据,每个测试数据只包含一个正整数N(1<=N<=10000),N代表死亡骑士手中钞票的面值.

注意:地精商店只有题中描述的三种道具.  
**Output**  
对于每组测试数据,请你输出死亡骑士最少要浪费多少钱给地精商人作为小费.  
**Sample Input**  
2  
900  
250  
**Sample Output**  
0  
50

思路：这道题有无数种解法，在这里我说一下母函数的做法。150，200，350是三个因子，起始系数全为0，因为N<=10000，所以终止系数分别为10000/150，10000/200，10000/350。每次输入的N就是最大的指数。求出答案数组后，从last往前搜，到第一个不为0的数所需的步数就是答案。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 10005;
    const int MOD = 30021;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    
    int Num;//因子个数
    int n1[MAXN];//n1[i]表示该乘积表达式第i个因子的起始系数
    int n2[MAXN];//n2[i]表示该乘积表达式第i个因子的终止系数
    int v[MAXN];//v[i]表示该乘积表达式第i个因子的权重
    int P;//P是可能的最大指数
    int a[MAXN], b[MAXN];//a为计算结果，b为中间结果。
    int last;
    
    void solve()
    {
        //初始化a，因为有last，所以这里无需初始化其他位 
        a[0] = 1;
        last = 0;
        for (int i = 1; i <= Num; i++)
        {
            int last2 = min(last + n2[i] * v[i], P);//计算下一次的last 
            memset(b, 0, sizeof(int)*(last2 + 1));//只清空b[0..last2] 
            for (int j = n1[i]; j <= n2[i] && j*v[i] <= last2; j++)//这里是last2 
                for (int k = 0; k <= last&&k + j*v[i] <= last2; k++)//这里一个是last，一个是last2 
                    b[k + j*v[i]] += a[k];
            memcpy(a, b, sizeof(int)*(last2 + 1));//b赋值给a，只赋值0..last2 
            last = last2;//更新last 
        }
    }
    
    void init()
    {
        Num = 3;
        n1[1] = 0; n1[2] = 0; n1[3] = 0;
        n2[1] = 66; n2[2] = 50; n2[3] = 28;
        v[1] = 150; v[2] = 200; v[3] = 350;
    }
    
    int main()
    {
        int T;
        int ans;
        init();
        scanf("%d", &T);
        while (T--)
        {
            ans = 0;
            scanf("%d", &P);
            solve();
            for (int i = last; i > 0; i--,ans++)
                if (a[i] != 0)
                    break;
            printf("%d\n", ans);
        }
    }