前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >PAT「1004 To Buy or Not to Buy - Hard Version (35分)」

PAT「1004 To Buy or Not to Buy - Hard Version (35分)」

作者头像
hotarugali
发布2022-03-01 15:46:13
3910
发布2022-03-01 15:46:13
举报

1. 题目

题目链接:PAT「1004 To Buy or Not to Buy - Hard Version (35分)」

Description

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 3extra 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 (\leq 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:

代码语言:javascript
复制
RYg5
8
gY5Ybf
8R5
12346789
gRg8h
5Y37
pRgYgbR52
8Y
8g

Sample Output 1:

代码语言:javascript
复制
Yes 3

Sample Input 2:

代码语言:javascript
复制
YrRR8RRrY
3
ppRGrrYB225
8ppGrrB25
Zd6KrY

Sample Output 2:

代码语言:javascript
复制
No 3

2. 题解

分析

初一看题,以为是 dp,然后发现状态太多了,根本无法 dp,左思右想没有好办法,只能暴力 dfs + 剪枝了(如果有其他更好的解法,希望大佬告知 :) 感谢 ),由于 PAT 上的数据太弱了,这都能过!剪枝主要考虑两个:

  • 如果所有珠子串都用上仍然无法满足要求,则直接退出 bfs
  • 如果 bfs 当前发现多余的珠子比原来的答案还多,则直接剪掉当前分支;如果当前刚好满足要求且多余的珠子数比原来的答案少,则更新当前答案

代码

代码语言:javascript
复制
#include <bits/stdc++.h>
#define INF 1e7
using namespace std;

const int MAXN = 110, MAXLEN = 1010, MAXCHAR = 62;

char str[MAXLEN];
char strs[MAXN][MAXLEN];
int bead[MAXCHAR];
int beads[MAXN][MAXCHAR];
int len_str;
int len_strs[MAXN];
int ans = INF;
int res = -1;

// 字母映射到连续数值
int maping(char ch) {
    int ans;
    if(ch <= '9') {
        ans = ch - '0';
    } else if(ch <= 'Z') {
        ans = ch - 'A' + 10;
    } else {
        ans = ch - 'a' + 36;
    }
    return ans;
}

// 计算每个珠子串对应珠子的个数
void genBead(int n) {
    len_str = 0;
    while(str[len_str]) {
        ++bead[maping(str[len_str++])];
    }
    
    for(int i = 0; i < n; ++i) {
        int len = 0;
        while(strs[i][len]) {
            ++beads[i][maping(strs[i][len++])];
        }
        len_strs[i] = len;
    }
}

// 暴力 bfs + 剪枝
void dfs(int sans, int x, int n) {
    // 如果全部珠子串都无法集齐所有珠子则直接退出(剪枝)
    if(res > 0) {
        return;
    }
    // 保存现场
    int curlen_str;
    int curbead[MAXCHAR];
    curlen_str = len_str;
    memcpy(curbead, bead, sizeof(bead));
    for(int i = 0; i < MAXCHAR; ++i) {
        int y = min(bead[i], beads[x][i]);
        len_str -= y;
        bead[i] -= y;
    }
    int use = curlen_str - len_str;
    int curans = sans + len_strs[x] - use;
    // 记录所有珠子串都用上还差的珠子数
    if(x == n-1 && res == -1) {
        res = len_str;
    }
    if(curans < ans) {
        // 如果当前代价小于答案才继续 bfs(剪枝)
        if(len_str) {
            for(int i = x+1; i < n; ++i) {
                dfs(curans, i, n);
            }
        } else {
            ans = curans;
            res = 0;
        }
    }
    // 恢复现场
    len_str = curlen_str;
    memcpy(bead, curbead, sizeof(bead));
    return;
}

// 计算答案
void answer(int n) {
    for(int i = 0; i < n; ++i) {
        dfs(0, i, n);
    }
}

int main() 
{
    ios::sync_with_stdio(false);
    int n;
    scanf("%s%d", str, &n);
    for(int i = 0; i < n/2; ++i) {
        scanf("%s", strs[i]);
    }
    for(int i = n-1; i >= n/2; --i) {
        scanf("%s", strs[i]);
    }
    genBead(n);
    answer(n);
    if(ans < INF) {
        printf("Yes %d\n", ans);
    } else {
        printf("No %d\n", res);
    }
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-08-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目
    • Description
      • Input Specification:
        • Output Specification:
          • Sample Input 1:
            • Sample Output 1:
              • Sample Input 2:
                • Sample Output 2:
                • 2. 题解
                  • 分析
                    • 代码
                    领券
                    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档