锐客网

  1. 首页 > it技术 > >

Codeforces580|Codeforces580 D. Kefa and Dishes（状压dp）

题意： 有n盘菜,现在你要吃m盘菜,每种菜只能吃一次
吃第i盘菜可以得到a(i)的满足感,
同时给出k条规则(x,y,c),
表示如果在吃y之前刚好吃过了x,那么就会得到c的满足感,
(注意x和y之间没有其他菜)
问吃m盘菜的最大满足感是多少.
【Codeforces580|Codeforces580 D. Kefa and Dishes（状压dp）】数据范围：n<=18，k<=n*(n-1)
解法：

d[sta][i]表示当前已经吃的状态为sta,最后吃的菜是i的最大满足感, 状压dp,枚举下一个吃的菜进行转移就行了

code：
#include using namespace std; #define int long long const int maxm=20; vector >g[20]; int d[1<<20][20]; int cnt[1<<20]; int a[20]; int n,m,k; int cal(int x){ int ans=0; while(x){ ans++; x&=(x-1); } return ans; } signed main(){ //预处理二进制中1的个数 for(int i=0; i<(1<<20); i++){ cnt[i]=cal(i); } // cin>>n>>m>>k; for(int i=0; i>a[i]; for(int i=1; i<=k; i++){ int a,b,c; cin>>a>>b>>c; a--,b--; g[a].push_back({b,c}); } for(int i=0; i=m)continue; for(int j=0; j>j&1){ for(int k=0; k>k&1)){ d[i^(1<>k&1)){ d[i^(1<

    推荐阅读


    上一篇：Codeforces22|Codeforces22 D. Segments（贪心）

    下一篇：UE4虚幻4学习|制作血条/蓝条/蓄力条等进度条（Progress Bar）