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

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
 

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

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