题目

原题链接
{% fold 点击显/隐题目 %}

Eva would like to make a string of beads with her favorite colors so she went to a small shop to buy some beads. There were many colorful strings of beads. However the owner of the shop would only sell the strings in whole pieces. Hence in some cases Eva might have to buy several strings to get all the beads she needs. With a hundred strings in the shop, Eva needs your help to tell her whether or not she can get all the beads she needs with the least number of extra beads she has to pay for.
For the sake of simplicity, let's use the characters in the ranges [0-9], [a-z], and [A-Z] to represent the colors. In sample 1, buying the 2nd and the last two strings is the best way since there are only 3 extra beads. In sample 2, buying all the three strings won't help since there are three "R" beads missing.

Input Specification:
Each input file contains one test case. Each case first gives in a line the string that Eva wants. Then a positive integer N (<=100) is given in the next line, followed by N lines of strings that belong to the shop. All the strings contain no more than 1000 beads.

Output Specification:
For each test case, print your answer in one line. If the answer is "Yes", then also output the least number of extra beads Eva has to buy; or if the answer is "No", then also output the number of beads missing from all the strings. There must be exactly 1 space between the answer and the number.

Sample Input 1:
RYg5 8 gY5Ybf 8R5 12346789 gRg8h 5Y37 pRgYgbR52 8Y 8g

Sample Output 1:
Yes 3

Sample Input 2:
YrRR8RRrY 3 ppRGrrYB225 8ppGrrB25 Zd6KrY

Sample Output 1:
No 3

{% endfold %}

解析

题目要求是使用n个字符串用其中的字符拼出来特定字符串，如果选择了一个字符串，那么多出来的字符算为浪费的值，求最小的浪费值；有可能无法拼出来要求的字符串，那么要算出来还缺几个字符。

数据量：字符串个数\(n<100\)，字符串长度\(L<1000\)
有考虑到背包和网络流，不过时间复杂度都不可能满足要求。只能搜索下，尽可能剪枝。

因为原则上时间复杂度是指数级（单递归已经是O(2^n)了），因此肯定需要逆天一样的剪枝技巧。

按照惯例先想下可能可行的剪枝，为了方便叙述，把浪费的值称作溢出（overflow）：

找到答案，更新答案值，直接返回答案；
发现下标已经超过了n，说明没找到答案，返回；
如果现在的答案（溢出）已经超过了已经跑出来的最优解，那么不可能得到更优解，剪枝；
如果已经跑出来的最有解是0，那么不可能有更优解，剪枝；
如果从当前跑到的下标开始，后面所有的链子全部选上，也不可能凑够，剪枝；
如果当前的链子压根没有当前需要的值，不跑选择当前链的分支，剪枝。

初步想到的剪枝就那么多，前两个是递归边界，3、4、5、6则是常见的一些剪枝套路。

因为字符可能是0-9，a-z，A-Z，因此需要先处理一下映射关系，方便后面操作。
共有10+26+26=62个取值，可以申请64的数组出来，存放每个字符的个数。

维护一个结构体来存储这些内容，简化dfs里要处理的内容。

按照上面的来说，对于每个链，需要记录这个链原有的信息：每种字符的个数，以及为了简化操作的信息：溢出的字符个数以及符合要求的字符个数。

然后再记录一个数组，记录i以后所有字符串，字符j的个数。为了进一步优化，再用j=63来记录符合要求的字符总数（对应剪枝5）

最后，判断下是否能得到解，如果无解，就不用跑dfs了，可以直接用上面数组i=0的数据来处理。

喜闻乐见的是最后一组数据过不掉。上网查了下，大家普遍都是用数据漏洞限制搜索次数强行出结果，然而我试了下，还是过不了……

又加了个判断是否有字符串直接就满足要求的情况，根据OJ的反馈，可以推测出最后一组是有两个字符串恰好是目标的两部分，因此溢出值是0，并且不是单纯的字符串满足要求，因此优化并没有帮助。

开始尝试针对这个特殊情况优化，发现如果有多个字符串是目标字符串的子集，在保证他们不溢出的情况下，可以直接把他们拼到一起，不影响结果。因此想到了先背包处理一下，把能拼一起的拼到一起，然而算了下复杂度，铁定超时。

但是这个拓展了思路：应该先处理overflow小的字符串，这样能更快找到答案，剩下的就可以依靠剪枝剪掉了。
用sort处理一下，完美解决最后一组样例。

不过可能还有能卡掉我的程序的数据。

代码

C++解法

{% fold 点击显/隐题目 %}

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
using namespace std;

#define Log(format, ...) // printf(format, ##__VA_ARGS__)

const int maxn = 105;
const int maxL = 1005;
const int INF = (2u << 30) - 1;

struct BeadString {
    static int beadColorType;
    static int colorMap[64];

    int cnt[64];
    int neededBeads;
    int overflow;

    static int getBeadColorValue(char c) {
        int value = 0;
        if (c >= '0' && c <= '9')
            value = c - '0';
        else if (c >= 'a' && c <= 'z')
            value = c - 'a' + 10;
        else
            value = c - 'A' + 10 + 26;
        return value;
    }
    static int getBeadColorIndex(char c) {
        return colorMap[getBeadColorValue(c)];
    }

    static BeadString setBeadColorType(string s) {
        beadColorType = 0;
        memset(colorMap, -1, sizeof(colorMap));

        for (char c : s) {
            int value = getBeadColorValue(c);
            if (colorMap[value] == -1)
                colorMap[value] = beadColorType++;
        }

        return BeadString(s);
    }

    BeadString() {}
    BeadString(string s) {
        neededBeads = overflow = 0;
        memset(cnt, 0, sizeof(cnt));
        for (char c : s) {
            int idx = getBeadColorIndex(c);
            if (idx == -1)
                ++overflow;
            else
                ++cnt[idx], ++neededBeads;
        }
    }

    bool operator<(const BeadString &rhs) const {
        return overflow < rhs.overflow;
    }

    void debug() {
        Log("neededBeads = %d  overflow = %d\n", neededBeads, overflow);
        Log("idx\t");
        for (int i = 0; i < beadColorType; ++i)
            Log("%4d ", i);
        Log("\ncnt\t");
        for (int i = 0; i < beadColorType; ++i)
            Log("%4d ", cnt[i]);
        Log("\n");
    }
};

int BeadString::beadColorType = 0;
int BeadString::colorMap[64];

vector<BeadString> beadString;
int beadStringNumber = 0;

int lastBeads[maxn][64];

int ans = INF;
bool choose[maxn];


int dfs(int t, BeadString need) {
    Log("\ndfs(%d) lastBeads=%d ans=%d\n", t, lastBeads[t][63], ans);
    Log("idx\t");
    for (int i = 0; i < beadStringNumber; ++i)
        Log("%4d ", i);
    Log("\nchoose\t");
    for (int i = 0; i < beadStringNumber; ++i)
        Log("%4d ", choose[i]);
    Log("\n-------\nneed\n------\n");
    need.debug();

    // 找到答案
    if (need.neededBeads == 0 || ans == 0) {
        Log("Get ans\n");
        return ans = min(ans, need.overflow);
    }
    // 找到头，仍然没有答案
    if (t >= beadStringNumber) {
        Log("At end\n");
        return ans;
    }
    // 如果已经不可能比最优解好，剪枝
    if (need.overflow > ans) {
        Log("Cannot get best ans\n");
        return ans;
    }
    // 如果剩下的全部选上，也不能得到所有珠子，剪枝
    if (need.neededBeads > lastBeads[t][63]) {
        Log("No enough beads 0\n");
        return ans;
    }

    for (int i = 0; i < BeadString::beadColorType; ++i) {
        if (need.cnt[i] > lastBeads[t][i]) {
            Log("No enough beads 1\n");
            return ans;
        }
    }

    BeadString &nowBeadString = beadString[t];

    // 不选当前链
    int nowAns = dfs(t + 1, need);

    // 选择当前链
    // 只有当前链有需要的东西时，才尝试选择该链
    bool noNeed = false;

    if (nowBeadString.neededBeads)
        noNeed = false;

    for (int i = 0; noNeed == false && i < BeadString::beadColorType; ++i) {
        if (need.cnt[i] && nowBeadString.cnt[i])
            noNeed = false;
    }

    if (!noNeed) {
        choose[t] = true;
        Log("-------\nnowBeadString %d\n------\n", t);
        nowBeadString.debug();

        for (int i = 0; i < BeadString::beadColorType; ++i) {
            if (need.cnt[i] >= nowBeadString.cnt[i]) {
                need.cnt[i] -= nowBeadString.cnt[i];
                need.neededBeads -= nowBeadString.cnt[i];
            } else {
                need.neededBeads -= need.cnt[i];
                need.overflow += nowBeadString.cnt[i] - need.cnt[i];
                need.cnt[i] = 0;
            }
        }
        need.overflow += nowBeadString.overflow;

        nowAns = min(dfs(t + 1, need), nowAns);

        choose[t] = false;
    }

    return nowAns;
}

char s[maxL];
int main() {
    beadStringNumber = 0;

    scanf("%s%d", s, &beadStringNumber);
    BeadString request = BeadString::setBeadColorType(string(s));

    string compoud = "";
    for (int i = 0; i < beadStringNumber; ++i) {
        scanf("%s", s);
        beadString.push_back(string(s));
    }
    sort(beadString.begin(), beadString.end());

    // 预处理
    int missing = 0; // 缺少的珠子个数
    memset(lastBeads, 0, sizeof(lastBeads));
    for (int i = beadStringNumber - 1; i >= 0; --i) {
        // 记录该串后面所有串需要的珠子的总数
        lastBeads[i][63] = lastBeads[i + 1][63] + beadString[i].neededBeads;

        bool match = true;
        for (int j = 0; j < BeadString::beadColorType; ++j) {
            // 具体到每种颜色的数目
            lastBeads[i][j] = lastBeads[i + 1][j] + beadString[i].cnt[j];
            if (request.cnt[j] && (beadString[i].cnt[j] != request.cnt[j]))
                match = false; // 该串不能刚好满足要求
            if (i == 0 && request.cnt[j] > lastBeads[0][j])
                missing += request.cnt[j] - lastBeads[0][j];
        }
        if (match && beadString[i].overflow == 0)
            ans = 0; // 存在和要求完全相同的串
    }

    memset(choose, 0, sizeof(choose));

    if (missing) {
        printf("No %d\n", missing);
    } else {
        printf("Yes %d\n", dfs(0, request));
    }
    return 0;
}

{% endfold %}

PAT顶级 1004.To Buy or Not to Buy - Hard Version

题目

解析

代码

C++解法