题解 CF417D

\(m\le 20\)，状压 DP。

首先可以根据每个人的 \(k\) 从小到大排序。

定义 \(f_{i,j}\) 表示考虑到第 \(i\) 个人，完成了 \(j\) 状态的题目，不考虑显示器所需的最小价格。

转移显然为 \(f_{i,j|s_i}=\min(f_{i-1,j}+x_i)\)。

最终答案为 \(ans=\min\limits_{i=1}^{n}f_{i,S}+b\cdot k_i\)。

考虑到当前状态只与上一个有关，滚动数组。

复杂度 \(O(n2^m)\)。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e6,N2=100+5,inf=LLONG_MAX>>1;
ll n,m,b,f[2][N],minn=inf;
struct node{ll x,k,m,s;}a[N2];
bool cmp(node x,node y){return x.k<y.k;}
int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n>>m>>b;
  for(int i=1;i<=n;++i){
    cin>>a[i].x>>a[i].k>>a[i].m;
    int x;
    for(int j=1;j<=a[i].m;++j){
      cin>>x;
      a[i].s|=(1<<(x-1));
    }
  }
  sort(a+1,a+n+1,cmp);
  for(int i=1;i<(1<<m);++i)f[0][i]=inf;
  int t=1;
  for(int i=1;i<=n;++i){
    for(int j=0;j<(1<<m);++j)f[t][j]=f[t^1][j];
    for(int j=0;j<(1<<m);++j)f[t][j|a[i].s]=min(f[t][j|a[i].s],f[t^1][j]+a[i].x);
    minn=min(minn,f[t][(1<<m)-1]+b*a[i].k);
    t^=1;
  }
  if(minn==inf)cout<<-1<<endl;
  else cout<<minn<<endl;
  return 0;
}