欢迎访问我的pat顶级题解目录哦 https://blog.****.net/richenyunqi/article/details/86751676

题目描述

算法设计

这道题没什么好办法，只能进行迭代搜索，在搜索过程中进行一些剪枝。本题有一组数据非常严格，我考虑了无数种正确的剪枝方案，也不能通过。显然搜索次数过多就造成了超时，为了AC这道题，我只能采取一些投机取巧的方法，设置一个跳出搜索的变量loop，每进行一次搜索就递增一次loop，当loop达到200次时，就结束搜索，将得到的当前解作为最优解进行输出。实践证明，本题的测试数据还是比较水的，两百次内搜索得到的解就是最优解。
下面阐述解决本题的算法，读者可以参考我的代码进行理解：
首先针对第一行需要进行匹配的字符串，定义一个unordered_map<char,int>trans变量将每一个字符都映射成一个数字作为数组下标，然后将每个字符出现的次数放入vector<int>need的相应位置。对其他字符串进行类似的操作，只统计这些字符串中在第一行字符串中出现的字符，并放入到一个vector<int>v变量中的相应位置。应该保证need数组和v数组同样的下标下代表相同字符的出现次数，以方便后续比较。最后在need和v数组末尾插入整个字符串的长度。将v数组全部放入到vector<vector<int>>strings变量中。
接着对strings按数组最后一个元素即字符串长度从短到长进行排序。
然后进行DFS搜索，搜索过程中，主要维护3个变量：

1. index：表示当前处理的字符串在strings中的下标
2. extra：表示处理当前字符串前，没有匹配成功的多余字符的数量
3. need数组：表示需要进行匹配的字符串没有匹配成功的字符及其数量的情况

此外还要维护两个全局变量：
4. Extra：表示匹配成功时最少的多余字符的数量
5. Remain：表示匹配失败时还有多少个字符没有匹配成功，当匹配成功时Remain=0

具体DFS搜索的算法可以直接参考我的代码，代码中已经添加了足够充分的注释。

C++代码

#include<bits/stdc++.h>
using namespace std;
unordered_map<char,int>trans;
vector<vector<int>>strings;
int Extra=INT_MAX,Remain=INT_MAX;//匹配成功时最少的多余字符的数量、匹配失败时还有多少个字符没有匹配成功
void DFS(int index,vector<int>need,int extra,int&loop){
    if(extra>=Extra||loop>=200)//当当前多余字符数量大于等于最小多余字符数量或者搜索次数达到200次时结束搜索
        return;
    ++loop;//进行一次搜索递增一次loop
    int use=0;//当前字符串匹配成功的字符数量
    for(int i=0;i<need.size()-1;++i)//遍历出现的字符
        if(strings[index][i]>0)//当前字符串也出现了相应字符，更新相关变量
            if(strings[index][i]>need[i]){
                use+=need[i];
                need[i]=0;
            }else{
                use+=strings[index][i];
                need[i]-=strings[index][i];
            }
    extra+=strings[index].back()-use;//多余字符等于字符串字符总数-匹配成功的字符数量
    need.back()-=use;//更新没有匹配成功的字符数量
    if(need.back()==0){//所有字符均匹配成功
        Extra=min(Extra,extra);//更新最小多余字符数量
        Remain=0;//所有字符均匹配成功
        return;
    }
    if(index==strings.size()-1){//到达最后一个字符串
        Remain=min(need.back(),Remain);//更新Remain
        return;
    }
    for(int i=index+1;i<strings.size();++i)//继续进行搜索
        DFS(i,need,extra,loop);
}
int main(){
    string s;
    int n;
    cin>>s>>n;
    vector<int>need;//储存需要进行匹配的字符串的字符出现次数
    for(char c:s){//遍历字符串
        if(trans.find(c)==trans.end()){//该字符没出现过
            trans.insert({c,trans.size()});//插入trans中
            need.push_back(0);//插入need中
        }
        ++need[trans[c]];//递增该字符出现次数
    }
    need.push_back(s.size());//在need末尾插入该字符串的字符总数
    while(n--){
        cin>>s;
        vector<int>v(need.size(),0);//每个字符串维护一个与进行匹配的字符串相同长度的数组
        for(char c:s)//遍历字符串
            if(trans.find(c)!=trans.end())//只统计在进行匹配的字符串中出现的字符出现次数
                ++v[trans[c]];
        v.push_back(s.size());//在末尾插入该字符串的字符总数
        strings.push_back(v);//放入strings中
    }
    sort(strings.begin(),strings.end(),[](const vector<int>&b1,const vector<int>&b2){
        return b1.back()<b2.back();
    });//按字符串长度从短到长排序
    int loop=0;//结束搜索的变量
    for(int i=0;i<strings.size()&&loop<200;++i)//遍历所有的字符串，当搜索次数达到200次跳出循环
        DFS(i,need,0,loop);//进行搜索
    if(Remain==0)
        printf("Yes %d\n",Extra);
    else
        printf("No %d\n",Remain);
    return 0;
}