D. Kefa and Dishes(状压)

永久打开的传送门

\(这次总算没有写砸........\)

\(设f[i][j]为上一次吃的i物品状态为j的最大收益\)

\(那么我们就暴力枚举所有状态i，然后在当前状态找出一个没吃的食物j，再去找一个吃过的食物q\)

\(其中val[j]是食物j的收益，vis[q][j]是先吃q再吃j的收益\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[20][1<<20],vis[20][20],val[20],n,m,k;
bool isok(int i)
{
    ll ans=0;
    while(i)
    {
        if(i&1) ans++;
        i>>=1;
    }
    if(ans==m)  return true;
    else    return false;
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>val[i];
        f[i][1<<(i-1)]=val[i];
    }
    for(int i=1;i<=k;i++)
    {
        ll l,r,w;
        cin>>l>>r>>w;
        vis[l][r]=w;//先吃l再吃r获得w能量 
    }
    for(int i=0;i<(1<<n);i++)//枚举所有状态 
    for(int j=1;j<=n;j++)//枚举这一次吃的什么
    {
        int w=(1<<(j-1));
        if(w&i) continue;//已经吃过了
        for(int q=1;q<=n;q++)
        {
            if((1<<(q-1))&i)//吃过
                f[j][i+w]=max(f[j][i+w],f[q][i]+val[j]+vis[q][j]);
        }   
    }
    ll ans=0;
    for(int i=0;i<(1<<n);i++)
    if(isok(i))
    {
        for(int j=1;j<=n;j++)
            ans=max(ans,f[j][i]);
    }
    cout<<ans;
}