C# · 12月 20, 2021

cf580D. Kefa and Dishes(状压dp)

题意

$n$个食物,每个食物有一个满意度,从中选出$m$个,使得满意度最大

同时有$k$个关系:若$x_i$在$y_i$之前吃,则会获得$C_i$的代价

Sol

官方题解是$O(2^n n^2)$的,不过我没发现状态之间的联系,就写了一个$O(2^n n^3)$的,不过还是水过去了。

$f[i][j][sta]$表示现在已经放了$i$个,本轮要放第$j$个,状态为$sta$

转移的时候枚举一下上一个放了什么

/*

*/

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#define Pair pair

#define MP(x,y) make_pair(x,y)

#define fi first

#define se second

#define int long long

#define LL long long

#define rg register

#define sc(x) scanf(“%d”,&x);

#define pt(x) printf(“%d “,x);

#define db(x) double x

#define rep(x) for(int i = 1; i <= x; i++)

//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1<<22,stdin),p1 == p2) ? EOF : *p1++)

//char buf[(1 << 22)],*p1 = buf,*p2 = buf;

char obuf[1<<24],*O = obuf;

#define OS *O++ = ' ';

using namespace std;

using namespace __gnu_pbds;

const int MAXN = 1e6 + 10,INF = 1e9 + 10,mod = 1e9 + 7;

const double eps = 1e-9;

inline int read() {

char c = getchar(); int x = 0,f = 1;

while(c '9') {if(c == '-') f = -1; c = getchar();}

while(c >= '0' && c <= '9') x = x * 10 + c – '0',c = getchar();

return x * f;

}

void print(int x) {

if(x > 9) print(x / 10);

*O++ = x % 10 + '0';

}

int N,M,K;

int f[2][19][262145];

int lk[19][19],a[MAXN];

main() {

N = read(); M = read(); K = read();

for(int i = 1; i <= N; i++) a[i] = read();

for(int i = 1; i <= K; i++) {

int x = read(),y = read(),z = read();

lk[x][y] = z;

}

int lim = (1 << N) – 1,o = 0;

for(int i = 1; i <= M; i++) {

o ^= 1;

for(int sta = 0; sta <= lim; sta++) {

if((__builtin_popcount(sta)) != i) continue;

for(int j = 1; j <= N; j++) {//��һ�ֳԵ�ɶ

if(!(sta & (1 << j – 1))) continue;

for(int k = 1; k <= N; k++) {//��һ�ֳԵ�ɶ

if(sta & (1 << k – 1)) {

/*if(o == 0 && j == 2 && k == 1) {

puts(“GG”);

}*/

f[o][j][sta] = max(f[o][j][sta],f[o ^ 1][k][sta ^ (1 << j – 1)] + lk[k][j]);

}

}

}

}

}

// printf(“%dn”,f[o][2][lim]);

int ans = 0;

for(int i = 1; i <= N; i++) {

for(int sta = 0; sta <= lim; sta++) {

if((__builtin_popcount(sta)) != M) continue;

if(!(sta & (1 << i – 1))) continue;

int Now = f[o][i][sta];

for(int j = 1; j <= N; j++)

if(sta & (1 << j – 1)) Now += a[j];

ans = max(ans,Now);

}

}

cout << ans;

return 0;

}

/*

2 2 1

1 1

2 1 1

*/