压缩(维数+状态)dp
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
//#define int long long
#define vi vector<int>
int n,m,b;
struct node{
int x,k,cnt;
vector<int> e;
};
#define ll long long
// ll dp[101][1<<20];
void solve(){
cin>>n>>m>>b;
// vector<int> x(n+1),k(n+1),cnt(n+1);
int z=(1<<m);
vector<node> qwq(n+1);
// vector<vector<ll>> dp(n+1,vector<ll>(z,-1));
ll dp[z];
for(int j=0;j<z;j++)dp[j]=-1;
for(int i=1;i<=n;i++){
cin>>qwq[i].x>>qwq[i].k>>qwq[i].cnt;
for(int j=1;j<=qwq[i].cnt;j++){
int p;cin>>p;
qwq[i].e.push_back(p);
}
}
sort(qwq.begin()+1,qwq.end(),[&](node a,node b){
return a.k<b.k;
});
dp[0]=0;
qwq[0].k=0;
ll ans=-1;
for(int i=1;i<=n;i++){
int sum=0;
for(auto x:qwq[i].e)sum+=(1<<(x-1));
for(int j=0;j<z;j++)
if(dp[j]!=-1)
dp[j]=dp[j]+1ll*b*(qwq[i].k-qwq[i-1].k);
for(int j=0;j<z;j++){
if(dp[j]==-1)continue;
if(dp[j|sum]==-1)dp[j|sum]=dp[j]+qwq[i].x;
else dp[j|sum]=min(dp[j|sum],dp[j]+qwq[i].x);
}
if(dp[z-1]!=-1){
if(ans==-1)ans=dp[z-1];
else ans=min(ans,dp[z-1]);
}
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
solve();
}