55 lines
2.2 KiB
C++
55 lines
2.2 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
typedef long long LL;
|
||
|
||
const int N = 20;
|
||
int a[N], c[N][N];
|
||
int K;
|
||
int n, m;
|
||
LL f[1 << N][N], ans;
|
||
|
||
//统计某个状态中数字1的数量
|
||
int count(int x) {
|
||
int res = 0;
|
||
for (int i = 0; i < 32; i++) res += x >> i & 1;
|
||
return res;
|
||
}
|
||
|
||
int main() {
|
||
cin >> n >> m >> K;
|
||
for (int i = 0; i < n; i++) { //下标从0开始
|
||
cin >> a[i];
|
||
f[1 << i][i] = a[i]; //只吃一个的初始化
|
||
}
|
||
while (K--) {
|
||
int x, y, w;
|
||
cin >> x >> y >> w;
|
||
x--, y--; //状态压缩的套路
|
||
c[x][y] = w; //记录x,y的前后关联关系
|
||
}
|
||
for (int i = 0; i < (1 << n); i++) { //枚举所有状态
|
||
for (int j = 0; j < n; j++) { //枚举每一位
|
||
if ((i & (1 << j)) == 0) continue; //不包含j的不是本次要计算的状态
|
||
for (int k = 0; k < n; k++) { //枚举前一次最后一个菜k,看看会不会获取到更大的满意度
|
||
/*
|
||
1、本轮吃下j，最后形成i这样的状态，那么上轮没有j,状态为 i^(1<<j)
|
||
2、上轮的状态是固定的，那么上轮的什么是不固定的呢？
|
||
答案:最后吃的是什么不固定！我们需要枚举所有上轮最后一个菜吃的是什么东西。
|
||
很显然，上轮最后一个菜不能是j。
|
||
如果上轮最后一个菜是k,本轮还只能吃j，则本轮的结果中必然包含k!
|
||
如果不包含k,那么k是天上掉下来的吗？这就是本题的状态之间关联关系的推导过程
|
||
由此可见，状态压缩DP的精髓在于：
|
||
状态的转移关系确定！
|
||
*/
|
||
if (j == k || (!(i & (1 << k))))continue;//相同或没吃过k不合法
|
||
//dp转移方程
|
||
f[i][j] = max(f[i][j], f[i ^ (1 << j)][k] + a[j] + c[k][j]);
|
||
}
|
||
//已经吃了m个菜就统计答案
|
||
if (m == count(i))ans = max(ans, f[i][j]);
|
||
}
|
||
}
|
||
printf("%lld\n", ans);
|
||
return 0;
|
||
} |