A25064. 买还是不买
填空题
困难
知识点
题目描述
买还是不买
题目描述
小红想用自己喜欢的彩色珠子做一条珠串，于是去一家小店买珠子。店里有很多条彩色的珠串，但店主只卖整串，不拆散零售珠子。于是小红为了得到自己喜欢颜色的珠子，就得买很多条现成的珠串，回家拆了自己拼。
由于店里有上百条珠串，小红只好求助于你，请你写个程序，帮她看看是否有可能买到所有她喜欢颜色的珠子，并且使得多余的珠子尽可能少。
为简单起见，我们用数字 0 到 9、以及英文的 26 个字母的大小写来表示珠子的颜色（即珠子最多有 62 种颜色）。
在样例 1 中，买第 2 条和最后两条珠串是最划算的，因为这样只有 3 颗珠子是多余的。
在样例 2 中，把全部三条珠串都买下也不行，因为还少三颗 R 珠。
输入
输入第一行给出小红想要的珠串。下一行给出正整数 N（≤ 100），随后 N 行，每行给出店里的一条珠串。所有珠串中的珠子不超过 1000 颗。
输出
如果能凑出小红想要的珠串，则在一行中输出 Yes、空格、最少的多余珠子的个数；否则输出 No、空格、凑不出来的珠子的个数。
样例输入1
RYg5
8
gY5Ybf
8R5
12346789
gRg8h
5Y37
pRgYgbR52
8Y
8g样例输出1
Yes 3样例输入2
YrRR8RRrY
3
ppRGrrYB225
8ppGrrB25
Zd6KrY样例输出2
No 3参考答案
//答案来源于AI
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <climits>
using namespace std;
const int MAX_COLOR = 62;
int getIndex(char c) {
if (c >= '0' && c <= '9')
return c - '0';
else if (c >= 'A' && c <= 'Z')
return 10 + (c - 'A');
else if (c >= 'a' && c <= 'z')
return 36 + (c - 'a');
return -1;
}
struct Bead {
int len;
vector<int> cnt;
string s;
Bead(string str) : s(str), len(str.size()), cnt(MAX_COLOR, 0) {
for (char c : str) {
int idx = getIndex(c);
if (idx != -1) {
cnt[idx]++;
}
}
}
};
vector<Bead> beads;
vector<int> target(MAX_COLOR, 0);
vector<int> total(MAX_COLOR, 0);
vector<vector<int>> suffix;
int best = INT_MAX;
int total_target = 0;
int N;
void dfs(int idx, vector<int> need, int cur_len) {
if (cur_len >= best) {
return;
}
int sum_need = 0;
bool all_zero = true;
for (int c = 0; c < MAX_COLOR; c++) {
if (need[c] > 0) {
all_zero = false;
sum_need += need[c];
}
}
if (all_zero) {
best = cur_len;
return;
}
if (idx >= N) {
return;
}
for (int c = 0; c < MAX_COLOR; c++) {
if (need[c] > suffix[idx][c]) {
return;
}
}
if (cur_len + sum_need >= best) {
return;
}
dfs(idx + 1, need, cur_len);
bool useful = false;
for (int c = 0; c < MAX_COLOR; c++) {
if (beads[idx].cnt[c] > 0 && need[c] > 0) {
useful = true;
break;
}
}
if (useful) {
vector<int> new_need = need;
for (int c = 0; c < MAX_COLOR; c++) {
if (new_need[c] > 0) {
new_need[c] = max(0, new_need[c] - beads[idx].cnt[c]);
}
}
dfs(idx + 1, new_need, cur_len + beads[idx].len);
}
}
int main() {
string target_str;
getline(cin, target_str);
total_target = target_str.size();
for (char c : target_str) {
int idx = getIndex(c);
if (idx != -1) {
target[idx]++;
}
}
cin >> N;
cin.ignore();
beads.reserve(N);
for (int i = 0; i < N; i++) {
string s;
getline(cin, s);
beads.push_back(Bead(s));
}
for (int i = 0; i < MAX_COLOR; i++) {
total[i] = 0;
}
for (int i = 0; i < N; i++) {
for (int c = 0; c < MAX_COLOR; c++) {
total[c] += beads[i].cnt[c];
}
}
int shortage = 0;
bool overall_meet = true;
for (int c = 0; c < MAX_COLOR; c++) {
if (target[c] > total[c]) {
overall_meet = false;
shortage += (target[c] - total[c]);
}
}
if (!overall_meet) {
cout << "No " << shortage << endl;
return 0;
}
sort(beads.begin(), beads.end(), [](const Bead& a, const Bead& b) {
return a.len < b.len;
});
suffix.resize(N, vector<int>(MAX_COLOR, 0));
for (int c = 0; c < MAX_COLOR; c++) {
suffix[N - 1][c] = beads[N - 1].cnt[c];
}
for (int i = N - 2; i >= 0; i--) {
for (int c = 0; c < MAX_COLOR; c++) {
suffix[i][c] = beads[i].cnt[c] + suffix[i + 1][c];
}
}
best = INT_MAX;
dfs(0, target, 0);
cout << "Yes " << best - total_target << endl;
return 0;
}
上一题
下一题