2010-1162

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意：
于指导要帮大家买4天的蛋饼，蛋饼有若干种料可以加，每种料都有价钱，还有一种特殊的料Z，不用钱。
第一天大家要买的蛋饼单都已经告诉于指导了，于指导必须照着买。
从第二天起，于指导可以安排每个人的蛋饼料都加什么。
但是每个人从第二天起蛋饼的料都要不同于其他任何人的蛋饼，并且与之前于指导买过的所有蛋饼料都不同。
不同可表现为加入的料不同，或者某种料的数量不同。
而且每个人每天的蛋饼价值都要与该人第一天给于指导下的单的价值一样。
问于指导有多少种不同的安排方案。

解法：
题意很复杂，其实就是先A-Y做背包，得到总价值为x的方案数dp[x]，先将第一天已被order过的方案数减一下。
这里有一个trick，第一天的order可能有相同的，要特别处理一下。
剩下的就是简单的乘法原理计算一下了。res *= dp[x] * (dp[x] - 1]) *(dp[x] - 2); dp[x] -= 3;

代码：
{{{
#include <cstdio>
#include <cstring>
#include <string>
#include <utility>
#include <algorithm>
using namespace std;

const int MAXN = 100 + 1;
const int MAXL = 1024 + 1;
const int MOD = 10007;

int M, P, cost[MAXL], dp[MAXN];
pair <string, int> cake[MAXN];
char word[MAXL];

inline int getValue(string & word) {
    int res = 0;
    for (int i = 0; i < (int)word.size(); i++) {
        res += cost[(int)word[i]];
    }
    return res;
}

int main() {
    while (scanf("%d%d", &M, &P) != EOF && M && P) {
        memset(cost, 0, sizeof(cost));
        for (int i = 0; i < M; i++) {
            int tmp;
            scanf("%s%d", word, &tmp);
            cost[(int)word[0]] = tmp;
        }
        for (int i = 0; i < P; i++) {
            scanf("%s", word);
            string str = word;
            sort(str.begin(), str.end());
            while (str[(int)str.size() - 1] == 'Z') str.erase((int)str.size() - 1);
            cake[i] = make_pair(str, getValue(str));
        }
        sort(cake, cake + P);
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for (int i = 'A'; i < 'Z'; i++) {
            if (!cost[i]) continue;
            for (int j = 0; j < MAXN; j++) {
                if (j + cost[i] < MAXN) {
                    dp[j + cost[i]] += dp[j];
                    if (dp[j + cost[i]] >= MOD) dp[j + cost[i]] -= MOD;
                }
            }
        }
        for (int i = 0; i < P; i++) {
            if (!i || cake[i] != cake[i - 1]) {
                dp[cake[i].second]--;
            }
        }
        int res = 1;
        for (int i = 0; i < P; i++) {
            for (int j = 0; j < 3; j++) {
                res = (res * dp[cake[i].second]--) % MOD;
            }
        }
        if (res < 0) res += MOD;
        printf("%d\n", res);
    }
    return 0;
}
}}}

题意：

于指导要帮大家买4天的蛋饼，蛋饼有若干种料可以加，每种料都有价钱，还有一种特殊的料Z，不用钱。

第一天大家要买的蛋饼单都已经告诉于指导了，于指导必须照着买。

从第二天起，于指导可以安排每个人的蛋饼料都加什么。

但是每个人从第二天起蛋饼的料都要不同于其他任何人的蛋饼，并且与之前于指导买过的所有蛋饼料都不同。

不同可表现为加入的料不同，或者某种料的数量不同。

而且每个人每天的蛋饼价值都要与该人第一天给于指导下的单的价值一样。

问于指导有多少种不同的安排方案。

解法：

题意很复杂，其实就是先A-Y做背包，得到总价值为x的方案数dp[x]，先将第一天已被order过的方案数减一下。

这里有一个trick，第一天的order可能有相同的，要特别处理一下。

剩下的就是简单的乘法原理计算一下了。res *= dp[x] * (dp[x] - 1]) *(dp[x] - 2); dp[x] -= 3;

代码：

#include <cstdio>
#include <cstring>
#include <string>
#include <utility>
#include <algorithm>
using namespace std;
const int MAXN = 100 + 1;
const int MAXL = 1024 + 1;
const int MOD = 10007;
int M, P, cost[MAXL], dp[MAXN];
pair <string, int> cake[MAXN];
char word[MAXL];
inline int getValue(string & word) {
    int res = 0;
    for (int i = 0; i < (int)word.size(); i++) {
        res += cost[(int)word[i]];
    }
    return res;
}
int main() {
    while (scanf("%d%d", &M, &P) != EOF && M && P) {
        memset(cost, 0, sizeof(cost));
        for (int i = 0; i < M; i++) {
            int tmp;
            scanf("%s%d", word, &tmp);
            cost[(int)word[0]] = tmp;
        }
        for (int i = 0; i < P; i++) {
            scanf("%s", word);
            string str = word;
            sort(str.begin(), str.end());
            while (str[(int)str.size() - 1] == 'Z') str.erase((int)str.size() - 1);
            cake[i] = make_pair(str, getValue(str));
        }
        sort(cake, cake + P);
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for (int i = 'A'; i < 'Z'; i++) {
            if (!cost[i]) continue;
            for (int j = 0; j < MAXN; j++) {
                if (j + cost[i] < MAXN) {
                    dp[j + cost[i]] += dp[j];
                    if (dp[j + cost[i]] >= MOD) dp[j + cost[i]] -= MOD;
                }
            }
        }
        for (int i = 0; i < P; i++) {
            if (!i || cake[i] != cake[i - 1]) {
                dp[cake[i].second]--;
            }
        }
        int res = 1;
        for (int i = 0; i < P; i++) {
            for (int j = 0; j < 3; j++) {
                res = (res * dp[cake[i].second]--) % MOD;
            }
        }
        if (res < 0) res += MOD;
        printf("%d\n", res);
    }
    return 0;
}