题意：
有n盘菜,现在你要吃m盘菜,每种菜只能吃一次
吃第i盘菜可以得到a(i)的满足感,
同时给出k条规则(x,y,c),
表示如果在吃y之前刚好吃过了x,那么就会得到c的满足感,
(注意x和y之间没有其他菜)
问吃m盘菜的最大满足感是多少.
数据范围：n<=18，k<=n*(n-1)
解法：
d[sta][i]表示当前已经吃的状态为sta,最后吃的菜是i的最大满足感,
状压dp,枚举下一个吃的菜进行转移就行了
code：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=20;
vector<pair<int,int> >g[20];
int d[1<<20][20];
int cnt[1<<20];
int a[20];
int n,m,k;
int cal(int x){int ans=0;while(x){ans++;x&=(x-1);}return ans;
}
signed main(){//预处理二进制中1的个数for(int i=0;i<(1<<20);i++){cnt[i]=cal(i);}//cin>>n>>m>>k;for(int i=0;i<n;i++)cin>>a[i];for(int i=1;i<=k;i++){int a,b,c;cin>>a>>b>>c;a--,b--;g[a].push_back({b,c});}for(int i=0;i<n;i++){d[1<<i][i]=a[i];}for(int i=0;i<(1<<n);i++){if(cnt[i]>=m)continue;for(int j=0;j<n;j++){if(i>>j&1){for(int k=0;k<n;k++){if(!(i>>k&1)){d[i^(1<<k)][k]=max(d[i^(1<<k)][k],d[i][j]+a[k]);}}for(auto p:g[j]){int k=p.first,v=p.second;if(!(i>>k&1)){d[i^(1<<k)][k]=max(d[i^(1<<k)][k],d[i][j]+a[k]+v);}}}}}int ans=0;for(int i=0;i<(1<<n);i++){if(cnt[i]==m){for(int j=0;j<n;j++){ans=max(ans,d[i][j]);}}}cout<<ans<<endl;return 0;
}