CF1042B 【Vitamins】（去重，状压搜索）

由题意,我们其实会发现

对于每一种果汁，其对应的状态只有可能有7种

VA​
VB​
VC​
VA+VB​
VA+VC​
VB+VC​
VA+VB+VC

　　　这道题就大大简化了

我们把所有果汁都读进来

每种状态取价格最小的（这才有可能最优）

（在这里我状压了一下，用二进制表示其种类）

之后爆搜即可

如果当前已满足（三种维生素都有了，答案就取min）

最后输出即可

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define rii register int i

#define rij register int j

using namespace std;

int bj[],zt[],n;

long long ans=;

void dfs(int wz,long long an,int ztz)

{

    if(ztz==)

    {

        ans=min(ans,an);

        return;

    }

    for(rii=wz+;i<=;i++)

    {

        if(zt[i]!=)

        {

            dfs(i,an+zt[i],ztz|i);

        }

    }

}

int main()

{

    scanf("%d\n",&n);

    for(rii=;i<=;i++)

    {

        zt[i]=;

    }

    for(rii=;i<=n;i++)

    {

        bj[]=;

        bj[]=;

        bj[]=;

        int ltt;

        int ztz=;

        scanf("%d ",&ltt);

        char l=getchar();

        while(l!=)

        {

            if(l=='A'&&bj[]==)

            {

                ztz|=;

                bj[]=;

            }

            if(l=='B'&&bj[]==)

            {

                ztz|=;

                bj[]=;

            }

            if(l=='C'&&bj[]==)

            {

                ztz|=;

                bj[]=;

            }

            l=getchar();

        }

        zt[ztz]=min(zt[ztz],ltt);

    }

    dfs(,,);

    if(ans>=)

    {

        cout<<"-1";

    }

    else

    {

        cout<<ans;

    }

}