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
2 2 1
1 1
2 1 1
3
4 3 2
1 2 3 4
2 1 5
3 4 2
12
Note样例1中，按照2，1的顺序，可以额外获得1点满意度。
样例2中，按4,2,1或者2,1,4，都可以额外获得5点满意度。
O(2 n* n 2).
#include <bits/stdc++.h> #define pb push_back using namespace std; const long long A=100000000000000LL,N=1228228; long long mask,i,j,n,m,k,a[N],b[N],x,y,z,c[21][21],o,ot,dp[N][21]; long long len(long long mask){ long long k=0; for(i=0;i<n;i++)if(mask&b[i])k++; return k; } int main(){ cin>>n>>m>>k; for(i=0;i<n;i++)scanf("%d",&a[i]); b[0]=1; for(i=1;i<=n;i++)b[i]=b[i-1]*2; while(k--)scanf("%d%d%d",&x,&y,&z),c[x-1][y-1]=z; for(i=0;i<n;i++)dp[b[i]][i]=a[i]; for(mask=0;mask<b[n];mask++)for(i=0;i<n;i++)if(mask&b[i]){ for(j=0;j<n;j++)if((mask&b[j])==0)dp[(mask|b[j])][j]=max(dp[(mask|b[j])][j],dp[mask][i]+c[i][j]+a[j]); } for(mask=0;mask<b[n];mask++)if(len(mask)==m)for(i=0;i<n;i++)o=max(o,dp[mask][i]); cout<<o<<"\n"; }
Kefa and Dishes CodeForces - 580D 位运算，dp
原文：https://www.cnblogs.com/xxxsans/p/12783774.html