370

# 题目

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

# 解析

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

# 代码

## C++解法

#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;
}

• 点击查看/关闭被识别为广告的评论