https://www.cnblogs.com/violet-acmer/p/9682082.html
题意：
如果可以通过喝果汁将维生素A,B,C全部摄取，求最小花费，如果不能，输出"-1"。
题解：
我的思路：每个果汁含有的维生素最多有7种可能，分别为
A B C
AB(BA) AC(CA) BC(CB)
ABC(ACB)(BAC)(BCA)(CAB)(CBA)
将其分别对应为数字1-7
设变量price[i]
price[1] : 只含维生素A的饮料的最小价钱
price[2] : 只含维生素B的饮料的最小价钱
price[3] : 只含维生素C的饮料的最小价钱
...........
price[7] : 只含维生素ABC的饮料的最小价钱，注意含有维生素ACB和其余四种情况都记录在只含维生素ABC里
易知price[ ]记录的是含某维生素的最小花费的饮料的假期那
当n个果汁的信息输入完后，price[ ]数组也初始化完毕。
接着将含有复合(例如含有维生素AB)维生素的price[ ] 与单个维生素的总价格比较，如果复合的更便宜，则不更新，如果单个的总价格更便宜，则更新复合的价格
例如price["AB"]=10,price["A"]=2,price["B"]=6;
显然有price["AB"] > price["A"]+price["B"];
所以更新price["AB"]=price["A"]+price["B"];
最后输出price["ABC"]。
注意不存在三种维生素的情况要输出"-1"。
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=; int n;
int price[];
bool vis[]; map<string,int>mymap; void Copy(string &s,char ss[])
{
int len=strlen(ss);
for(int i=;i < len;++i)
s += ss[i];
s += '\0';
}
void Initial()
{
mymap.clear();
memset(vis,false,sizeof vis);
memset(price,INF,sizeof price);
mymap["A"]=;
mymap["B"]=;
mymap["C"]=;
mymap["AB"]=mymap["BA"]=;
mymap["AC"]=mymap["CA"]=;
mymap["BC"]=mymap["CB"]=;
mymap["ABC"]=mymap["ACB"]=mymap["BAC"]=mymap["BCA"]=mymap["CAB"]=mymap["CBA"]=;
}
void Read()
{
scanf("%d",&n);
for(int i=;i <= n;++i)
{
int c;
string s;
scanf("%d",&c);
cin>>s;
if(price[mymap[s]] > c)
price[mymap[s]]=c;
}
}
void Process()
{
price[]=min(price[],price[]+price[]);
price[]=min(price[],price[]+price[]);
price[]=min(price[],price[]+price[]);
price[]=min(price[],min(min(price[]+price[],price[]+price[]),price[]+price[]));
price[]=min(price[],min(min(price[]+price[],price[]+price[]),price[]+price[]));
printf("%d\n",price[] >= INF ? -:price[]);//通过将所有的price[ ] 值设置为INF来判断ABC是否都存在
}
int main()
{
Initial();
Read();
Process();
}
参考大神dp代码%%%%%%%%
将ABC转化成二进制数：
A : 001
B : 010
C : 100
AB=BA=A | B=011
AC=CA=A | C=101
BC=CB=B | C=110
ABC=ACB=BAC=BCA=CAB=CBA=A | B | C =111
定义dp[i][j]
i的范围为[0,n] : 1 ->第1瓶饮料 ，2->第2瓶饮料，........，n->第n瓶饮料
j的范围为[0,7] : 1代表维生素A，2代表维生素B，....，7代表维生素ABC
第 j 列表示“添加上维生素 j 缺少的维生素所需的最少的花费”
例如当j=5，表示当前维生素 j 含有的维生素为AC，缺少维生素B，而维生素B可以从含有维生素B或含有维生素AB或含有维生素BC的饮料中获取，从中选取花费最少的饮料
初始化dp[0][0,1,....6]=INF; F[0,1,....n][7]=0;。
状态转移方程F[i][j]=min(F[i-1][j | Si]+Wi,F[i-1][j]);
Si : 第i瓶饮料含有的维生素
Wi : 第i瓶饮料的花费
dp[i][j] : 第i瓶饮料“添加上维生素 j 缺少的维生素所需的最少的花费”
dp[i-1][j | Si] + Wi : 当前饮料可以为维生素 j 补充维生素Si，还差维生素 (ABC - (j+Si) )，而 (i-1) 行的 ( j | Si ) 列表示的就是添加差的维生素 (ABC - (j+Si) )所需的最小花费
所以dp[i-1][j | Si] + Wi 表示维生素 j 在添加上当前维生素Si所需的最小花费，但dp[i][j]存储的是最小花费，故需要和之前的dp[i-1][ j ]比较一下，谁花费少要谁。
例如：
Input：
3
10 A
15 B
16 C
由状态转移方程生成的二维表格如图所示：
w : 第i瓶饮料的花费
S : 第i瓶饮料所包含的维生素
当i=1时
j=0 : dp[1][0]=min(dp[0][A|0]+10,dp[0][0]) // A | 0 = A = 1
当前 j 不含有任何维生素，缺少维生素ABC，所以需要从之前的饮料中找到含有维生素ABC的饮料，但维生素A是第一瓶饮料，所以在此之前并没有出现含维生素ABC的饮料，所以dp[0][0]=INF;
同理可得j=1,2,3,4,5时dp[0][j]=INF;
当j=6时 : dp[1][6]=min(dp[0][A | BC]+10,dp[0][0])// A | BC = ABC = 7
6代表的是维生素BC，缺少的是维生素A，而当前饮料含有维生素A，j + A后正好为ABC，不缺少维生素，这就是为什么初始化dp[0,....,n][7]=0的原因，
所以dp[1][6]=0+10=10;
当i=2时
j=0 : dp[2][0]=min(dp[1][B | 0]+15,dp[1][0]) // B | 0 = B = 2
同样， j=0时不含有任何维生素，缺少维生素ABC，当前饮料可以提供维生素B，还缺少维生素AC，但之前并未出现含有维生素C的饮料，所以dp[1][B | 0] + 15 = INF+15
而且之前的dp[1][0]=INF，所以dp[2][0]=INF;
同理当j=1,2,3时dp[1][j]=INF
j=4 : dp[2][4]=min(dp[1][B | C]+15,dp[1][4]) // B | C = BC = 6
4代表的是维生素C，缺少维生素AB，而当前饮料含有维生素B，j + B = BC，还缺少维生素A，而dp[1][B | C]= 10 表示的正好是目前添加维生素A所需的最少花费，
所以dp[2][4]=10+15=25;
其余情况参照上述描述;
AC代码如下
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=; struct Juice
{
int w;
char s[];
int a;
};
int n;
int dp[maxn][];
Juice juice[maxn]; void Read()
{
scanf("%d",&n);
for(int i=;i <= n;++i)
{
scanf("%d%s",&juice[i].w,juice[i].s);
int len=strlen(juice[i].s);
for(int j=;j < len;++j)
{
if(juice[i].s[j] == 'A')
juice[i].a |= ;//A <- 001
else if(juice[i].s[j] == 'B')
juice[i].a |= ;//B <- 010
else
juice[i].a |= ;//C <- 100
}
}
}
void Initial()
{
for(int i=;i <= n;++i)
dp[i][]=;
for(int j=;j < ;++j)
dp[][j]=INF;
}
void Process()
{
Initial();
for(int i=;i <= n;++i)
for(int j=;j < ;++j)
dp[i][j]=min(dp[i-][j|juice[i].a]+juice[i].w,dp[i-][j]);
printf("%d\n",dp[n][] >= INF ? -:dp[n][]);
}
int main()
{
Read();
Process();
return ;
}