状压DP

CF580D

题目链接
https://codeforces.com/problemset/problem/580/D
题目大意

思路
令dp[i][j]表示，吃菜状态为i，且最后一道菜为j的最大满足感！
代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 20;
int n, m, t, q;
int a[N],b[N * N][N * N];
ll dp[1 << N][N],ans;
// dp[i][j]表示状态为i时，吃最后一道菜为j时获得的最大满足感！
void solve() {
    cin >> n >> m >> q;
    for(int i = 0;i < n;++i) {
        cin >> a[i];
        dp[1 << i][i] = a[i];
    }
    for(int i = 0;i < q;++i){
        int x,y,c;cin >> x >> y >> c;
        --x;--y;
        b[x][y] = c;
    }
    for(int i = 0;i < (1 << n);++i){
        for(int j = 0;j < n;++j){
            // i 不 包 含 j
            if((i &(1 << j)) == 0) continue;
            for(int k = 0;k < n;++k){
                // i 中 不 包 含 k
                if(j == k || (!(i &(1 << k)))) continue;
                // j 从 k 转移过来
                dp[i][j] = max(dp[i][j],dp[i ^ (1 << j)][k] + a[j] + b[k][j]);
            }
            if(__builtin_popcount(i) == m){
                ans = max(ans,dp[i][j]);
            }
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    t = 1;
    for (int _ = 0; _ < t; _++)
        solve();
    return 0;
}