CodeForces - 1042B Vitamins (思维)-白红宇

CodeForces - 1042B Vitamins (思维)

阅读量：2136 次

发布时间：2019-04-30

本文共 1323 字，大约阅读时间需要 4 分钟。

题目大意：

商店出售n中果汁，每种果汁含有一定量的维生素(维生素只有A、B、C三种)，每种果汁价格不同，问买果汁使得A、B、C三种维生素被都获取的最低价格是多少

题解：

最开始我的想法是，先将果汁按照价格从小到大排序，然后依次选择，知道ABC都含有了就break，然后再扫一遍已经选择的果汁，看看如果去掉当前果汁，总共的维生素是否还是都含有ABC，如果是，这个果汁就可以去掉。但是最后发现这个思路是不对的(但是过了23个点，WA24了，也是很神奇)

例如

A 10

B 10

C 10

ABC 20

显然是选ABC要好过选A+B+C，但是上述的做法就会只选了A+B+C就break了

这题没法通过排序什么的来贪心做，只能把所有情况都列举出来然后求最小

将所有可能产生ABC的组合都算一遍

ABC

A+B+C

AB+C

A+BC

AC+B

AB+BC

AC+BC

AC+AB

#include
   
    #include
    
     #define ll long long#define INF 1000000007using namespace std;map
     
      _map;int n;int get(string x,string y){    if(_map.count(x)&&_map.count(y))        return _map[x]+_map[y];    return INF;}int main(){    //freopen("input.txt","r",stdin);    cin>>n;    int cc;    string ss;    for(int i=1;i<=n;++i)    {        cin>>cc>>ss;        sort(ss.begin(),ss.end());        if(_map.count(ss)==0)        {            _map[ss]=cc;        }        else _map[ss]=min(_map[ss],cc);    }    int ans=INF;    if(_map.count("A") && _map.count("B") && _map.count("C"))        ans=_map["A"]+_map["B"]+_map["C"];    if(_map.count("ABC"))        ans=min(ans,_map["ABC"]);    ans=min(ans,get("AB","C"));    ans=min(ans,get("A","BC"));    ans=min(ans,get("AC","B"));    ans=min(ans,get("AB","BC"));    ans=min(ans,get("AC","BC"));    ans=min(ans,get("AC","AB"));    if(ans==INF)        ans=-1;    cout<
      
       <