Kefa and Dishes
Problem's Link
Mean:
菜单上有n道菜，需要点m道。每道菜的美味值为ai。
有k个规则，每个规则：在吃完第xi道菜后接着吃yi可以多获得vi的美味值。
问：最多可以获得多少美味值？
(1≤m≤n≤18,0≤k≤n∗(n−1))
analyse:
经典的状压DP。
由于最多18道菜，可用一个数s（s<=2^18）来唯一标识一种状态。
对于一个状态s，枚举两个位置i和j：i从已选择的菜中选定，j从未选择的菜中选定。
下一个状态ss的就是：吃完i后接着吃j的所有状态的最大值。
转移过程：ss=s|(1<<j)
状态转移方程：dp[ss][j]=max(dp[ss][j],dp[s][i]+sa[j]+ad[i][j])
答案就是所有选择数量达到m的状态的最大值。
Time complexity: O( (2^n) *( n^2) )