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

举报
楚楚冻人玥玥仙女 发表于 2021/11/19 01:46:57 2021/11/19
【摘要】 1004 To Buy or Not to Buy - Hard Version (35分) 题目传送门:1004 To Buy or Not to Buy - Hard Version (35分) ...

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

题目传送门:1004 To Buy or Not to Buy - Hard Version (35分)

一、题目大意

二、解题思路

dfs判断是否选取这一个

三、AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 110, C=130, MAX = 999999;
string t;
int n;
int exceed = MAX;
int M1[C], M3[C], EX[C];
int M2[N][C];
void dfs(int step, int ex){
  if(ex >= exceed)return;// 提前剪枝
  if(step>=n){
    for(int i = '0'; i <= 'z'; i++){
      if(M1[i] > EX[i]){
        return;
      }
    }
    exceed = ex;
    return;
  }
  int temp = ex;
  for(int i = '0'; i <= 'z'; i++){
    if(EX[i] > M1[i]){
      ex += M2[step][i];// 分两种情况计算超出的数量
    }else if(EX[i] + M2[step][i] > M1[i]){
      ex += EX[i] + M2[step][i] - M1[i];
    }
    EX[i] += M2[step][i];
  }
  dfs(step+1, ex);
  for(int i = '0'; i <= 'z'; i++){
    EX[i] -= M2[step][i];
  }
  dfs(step+1, temp);
}
int main(){
  freopen("input.txt", "r", stdin);
  cin >> t;
  for(int i = 0; i < t.size(); i++)M1[t[i]]++;
  cin >> n;
  string s;
  for(int i = 0; i < n; i++){
    cin >> s;
    for(int j = 0; j < s.size(); j++){
      M3[s[j]]++;
      M2[i][s[j]]++;
    }
  }
  int sum = 0;
  for(int i = '0'; i <= 'z'; i++){
    if(M1[i] > M3[i]){
      sum += M1[i] - M3[i];
    }
  }
  if(sum){
    cout << "No " << sum << endl;
    return 0;
  }
  dfs(0, 0);
  cout << "Yes " << exceed << endl;
}

  
 

文章来源: blog.csdn.net,作者:爱玲姐姐,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/jal517486222/article/details/104330191

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。