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

题意：

给你n种菜，吃每种菜都会得到对应的满足值。给出k种规则，如果先吃a再吃b 满足感就会提升c。

最后你要吃共m种菜，能获得的最大满足值为多少。

思路：

题目范围 最多18种菜。所以使用状态压缩DP。

f[S][i]为当前已选菜的状态为S，最后一个菜为i的最大满意度.

状态转移方程：

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

S1表示吃了j之后的新状态，S表示未吃j之前的状态，val[i][j]表示i之后向前吃j。

程序复杂度O（(2^n)*n*n）。

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

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

对应的二进制数：

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

如果集合的大小n<32,可以考虑使用状态压缩，

即用一个数i<(1<<n)表示一个子集合。