kefa进入了一家餐厅，这家餐厅中有n个菜（0<n<=18）,kefa对第i个菜的满意度为ai（0<=ai<=10^9），并且对于这n个菜有k个规则，如果kefa在吃完第xi个菜之后吃了第yi个菜（保证xi、yi不相等），那么会额外获得ci（0<=ci<=10^9）的满意度。kefa要吃m道任意的菜（0<m<=n），但是他希望自己吃菜的顺序得到的满意度最大，请你帮帮kefa吧！

输入第一行是三个数：n,m,k

第二行是n个数，第i个数表示kefa对第i道菜的满意度为ai

第三行到第k+2行每行有3个数：xi，yi，ci，表示如果kefa在吃完第xi道菜之后立刻吃了第yi道菜，则会额外获得ci的满意度

题解：状态压缩dp
dp[i][j] 表示i状态最后吃的菜为j的最大值
转移方程：
dp[i|(1<<j)][j] = max(dp[i][k] + dis[k][j] + a[k])

#include <bits/stdc++.h>
using namespace std;
const int maxn = 20;
typedef long long ll;
ll dp[1<<maxn][maxn], dis[maxn][maxn], a[1<<maxn];
int check(int x) {
    int ans = 0;
    while (x) {
        if (x & 1) ans++; 
        x >>= 1;
    }
    return ans;
}
int main() {
    int n, m, q;
    ll x, y, z;
    cin >> n >> m >> q;
    for (int i = 0; i < n; i++) {
        cin >> a[i]; 
        dp[1<<i][i] = a[i];
    }
    for (int i = 1; i <= q; i++) {
        cin >> x >> y >> z;
        x--; y--; dis[x][y] = max(dis[x][y], z);
    }
    for (int x = 0; x < (1 << n); x++) {
        for (int i = 0; i < n; i++) {
            if (!(x & (1 << i))) continue;
            for (int j = 0; j < n; j++) {
                if (i == j || (x & (1 << j))) continue;
                int xx = x | (1 << j);
                dp[xx][j] = max(dp[xx][j], dp[x][i] + dis[i][j] + a[j]);            
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < (1 << n); i++) {
        if (check(i) != m) continue;
        for (int j = 0; j < n; j++) ans = max(ans, dp[i][j]);
    }
    cout << ans << endl;
    return 0;
}