题意：有n个菜，每个菜有个兴奋值，并且如果吃饭第i个菜立即吃第j个菜，那么兴奋值加ma[i][j]，求吃m个菜的最大兴奋值，（n<=18）
分析：定义dp[status][last]，status为每道菜的状态，1为吃，0为不吃，last为最后一个菜，dp[status][last]，在status状态下最后吃last的最大兴奋值，然后枚举status去更新后面的状态，详细见代码
AC代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,k;
ll w[20],ma[20][20],dp[(1<<18)+10][20],ans=0;
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>k;
for(int i=0;i<n;i++)
cin>>w[i];
for(int i=1;i<=k;i++)
{
int a,b;
ll c;
cin>>a>>b>>c;
ma[a-1][b-1]=c;
}
for(int i=0;i<n;i++)
dp[(1<<i)][i]=w[i];
for(int i=0;i<(1<<n);i++)
{
int cnt=0;
for(int j=0;j<n;j++)//当前状态可以转移到“当前状态+一个菜”
{
if((i&(1<<j))==0)continue;
cnt++;
// cout<<cnt<<endl;
for(int k=0;k<n;k++)//找到一个当前状态不吃的菜，用当前状态去更新吃第k个菜的状态
{
if((i&(1<<k))==1)continue;
dp[(i^(1<<k))][k]=max(dp[(i^(1<<k))][k],dp[i][j]+w[k]+ma[j][k]);
}
}
if(cnt==m)
for(int j=0;j<n;j++)ans=max(ans,dp[i][j]);
}
cout<<ans<<endl;
return 0;
}