\(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;
}
标签:node,min,int,题解,ll,long,CF417D
From: https://www.cnblogs.com/HQJ2007/p/17561330.html