?https://codeforces.com/problemset/problem/580/D

題意：

給你n種菜，吃每種菜都會(huì)得到對(duì)應(yīng)的滿足值。給出k種規(guī)則，如果先吃a再吃b 滿足感就會(huì)提升c。

最后你要吃共m種菜，能獲得的最大滿足值為多少。

思路：

題目范圍 最多18種菜。所以使用狀態(tài)壓縮DP。

f[S][i]為當(dāng)前已選菜的狀態(tài)為S，最后一個(gè)菜為i的最大滿意度.

狀態(tài)轉(zhuǎn)移方程：

f[S1][j] = max(f[S1][j], f[S][i] + a[j] + val[i][j]);

S1表示吃了j之后的新狀態(tài)，S表示未吃j之前的狀態(tài)，val[i][j]表示i之后向前吃j。

程序復(fù)雜度O（(2^n)*n*n）。

集合{a,b,c}的所有子集合為：

{a}, , {c},{a,b},{a,c},{b,c},{a,b,c}

對(duì)應(yīng)的二進(jìn)制數(shù)：

1，10，100， 11，101，110，111

如果集合的大小n<32,可以考慮使用狀態(tài)壓縮，

即用一個(gè)數(shù)i<(1<<n)表示一個(gè)子集合。