传送门：点击打开链接
题意：有n种菜，现在选m种菜来吃，还有很多条好处，如果在吃y的前一道菜是x的话，那么就可以获得满意度。每一种菜都有一个满意度。
思路：...只能说Codeforces的测评机实在是太好了，n=18，O(n^2*2^n)复杂度的记忆化搜索代码都能在500ms跑出来，我自己本地跑了3秒多- -
如果你敢写O(n^2*2^n)复杂度的代码的话，那基本就做完了。设dp[i][S]表示为最后一道菜为i，现在的菜吃的状态为S。S中的二进位如果为1表示已经吃了，如果是0则表示没吃，然后一个记忆化搜索，答案就出了了。
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck printf("fuck")
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, LL> PIL;const int MX = 18;int n, m, k;
LL dp[MX][1 << MX], A[MX], G[MX][MX];LL DP(int u, int S, int cnt) {if(cnt == m) return 0;if(~u && ~dp[u][S]) return dp[u][S];LL ret = 0;for(int i = 0; i < n; i++) {if(!(S >> i & 1)) {LL val = u == -1 ? A[i] : G[u][i] + A[i];ret = max(ret, DP(i, S ^ (1 << i), cnt + 1) + val);}}if(~u) dp[u][S] = ret;return ret;
}int main() {//FIN;while(~scanf("%d%d%d", &n, &m, &k)) {memset(dp, -1, sizeof(dp));memset(G, 0, sizeof(G));for(int i = 0; i < n; i++) {scanf("%I64d", &A[i]);}for(int i = 0; i < k; i++) {int u, v; LL c;scanf("%d%d%I64d", &u, &v, &c);G[u - 1][v - 1] = c;}printf("%I64d\n", DP(-1, 0, 0));}return 0;
}