cf580D. Kefa and Dishes(状压dp)

概述本文章向大家介绍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@H_301_26@

#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 < '0' || 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

*/

总结

以上是内存溢出为你收集整理的cf580D. Kefa and Dishes(状压dp)全部内容，希望文章能够帮你解决cf580D. Kefa and Dishes(状压dp)所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。