牛客练习赛49 筱玛爱阅读(子集dp+桶判断)

筱玛爱阅读

题是好题,但我不会…

---

定义$dp[i]$为取出书状态为$i$时的最大免费值

但是每本书的价格是自己选定的,无法$dp$

但是仔细观察发现每本书并无区别(只会在最终方案存在一次)

所以我们考虑$dp[i]$会怎样被更新

$cnt[i]$表示状态$i$有$cnt[i]$个$1$,而价格数组$a$从大到小排好序

$Ⅰ.存在优惠方案是i的政策,此时$

$$dp[i]=a[cnt[i]]$$

很明显,取前$cnt[i]$个是最优的

$Ⅱ.使用了某种优惠方案x从状态j转移到i,此时满足x\oplus j==i$

$$dp[i]=dp[j]+a[cnt[i]]$$

因为$dp[j]$肯定是把前$cnt[j]$大的价格用掉的

又因为当前总共用了$cnt[i]$本书,所以目前最优的优惠是取第$a[cnt[i]]$价格的书

$Ⅲ.不使用优惠方案,单买第j本书转移而来,满足i\&(1<<j)不为0$

$$dp[i]=dp[i-(1<<j)]$$

一直取$max$即可

当然你可能会质疑为什么每次状态$i$都取价格前$i$大的?

会不会有后效性??

没关系,因为我们枚举了所有状态

因为假设$x$个优惠方案总共买了$k$本书,选前$k$大价格的肯定没错

而我们枚举过程中考虑了所有优惠方案的排列,所以没错

#include <bits/stdc++.h> using namespace std; int n,m,k,sumn; int a[16],cnt[1<<16],dp[1<<16]; bool vis[1<<16]; int one(int x) { int ans=0; while( x ){ ans+=(x&1); x>>=1; } return ans; } int main() { cin >> n >> m; for(int i=1;i<=n;i++) cin >> a[i],sumn+=a[i]; sort(a+1,a+1+n,greater<int>() ); for(int i=1;i<=m;i++) { int k,x,v=0; cin >> k; while( k-- ){ cin >> x; v+=(1<<(x-1)); } vis[v]=1; } for(int i=1;i<(1<<n);i++) cnt[i]=one(i); for(int i=0;i<(1<<n);i++) { if( vis[i] ) dp[i]=max( dp[i],a[cnt[i]] ); for(int j=i;j;j=(j-1)&i ) { int x=(i^j);//x是优惠方案 if( !vis[x] ) continue; dp[i]=max( dp[i],dp[j]+a[cnt[i]] ); } for(int j=0;j<n;j++) if( i&(1<<j) ) dp[i]=max( dp[i],dp[i-(1<<j)] ); } cout << sumn-dp[(1<<n)-1]; }