题干：

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的满意度

Examples

Input

2 2 1
1 1
2 1 1

Output

3

Input

4 3 2
1 2 3 4
2 1 5
3 4 2

Output

12

Note

样例1中，按照2，1的顺序，可以额外获得1点满意度。 
样例2中，按4,2,1或者2,1,4，都可以额外获得5点满意度。

 

解题报告：

   dp[i][j]，i代表已经吃过了哪些菜，j代表最后吃的是哪个菜，然后更新判断就好了。

AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[1<<18][20];
ll a[20],val[20][20];
ll n,m,k;
bool ok(ll x) {
	int res = 0;
	for(ll i = 1; i<=(1<<n); i<<=1) {
		if(i & x) res++;
	}
	if(res == m) return 1;
	else return 0;
}
int main()
{
	ll u,v;
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i = 1; i<=n; i++) {
		scanf("%lld",a+i);
	}
	for(int i = 1; i<=k; i++) {
		scanf("%lld%lld",&u,&v);
		scanf("%lld",&val[u][v]);
	}
	memset(dp,-1,sizeof dp);
	for(int i = 1; i<=n; i++) {
		dp[(1<<i-1)][i] = a[i];
	}
	for(int bit = 0; bit<=(1<<n)-1; bit++) {
		for(int i = 1; i<=n; i++) {
			if(dp[bit][i] == -1) continue;
			for(int j = 1; j<=n; j++) {
				if(i != j && (bit&(1<<(j-1))) ==0) {
					dp[bit|(1<<(j-1))][j] = max(dp[bit][i] + a[j] + val[i][j],dp[bit|(1<<(j-1))][j]);
				}
			}
		}
	}
	ll maxx = 0;
	for(int bit = 0; bit<=(1<<n)-1; bit++) {
		if(ok(bit)) {
			for(int i = 1; i<=n; i++) {
				maxx = max(maxx,dp[bit][i]);
			}
		}
	}
	printf("%lld\n",maxx);
	return 0 ;
}

总结：还是太菜了、、、、and  这种东西位运算啥的包装成函数最好。