Cunning Gena - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
ki表示显示器数量需求
这点对于dp来说是比较难解决的，所以我们按 k 进行升序排序，这样便可以处理 k 的问题(其实这点有点难想到)。
假设 dp[i][j] 为前i个物品，状态为 j 下的最小价格，那么转移的时候显然我们无法处理显示屏是在哪个人买的这一问题。
所以我们令 dp1[i][j] 为前i个物品，状态为 j 下的算显示屏最小价格
令 dp2[i][j] 为在dp1[i][j]的状态下前i个物品，状态为 j 下的不算显示屏最小价格,这样就能处理显示屏的问题
此时我们已经知道了 dp1[i-1][j] 和 dp2[i-1][j]的最小价格
那么对于第 i 个物品有选和不选的两个选择
不选:dp1[i][j]=min(dp1[i][j],dp1[i-1][j]) ,dp2[i][j]=min(dp2[i][j],dp2[i-1][j])
选：如果dp1[i][j|a[i].s]>=dp2[i-1][j]+a[i].need*b+a[i].cost,表示此时第 i 个物品可以选,与此同时更新dp2[i][j|a[i].s]
否则，表示此时第i个物品不可以选，由于第i个物品没选，此时dp2[i][j|a[i].s]也不能更新
利用滚动数组优化空间复杂度，同时及时更新滚动数组中上一维状态为INF。
初始化:dp1[0][0]=dp2[0][0]=0,其余都为INF
#include<bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back #define popb pop_back #define fi first #define se second #define popcount __builtin_popcount #define popcountll __builtin_popcountll const int N=210; //const int M=; //const int inf=1e9; const ll INF=2e18; int T,n,m; ll b,dp1[3][(1<<21)+10],dp2[3][(1<<21)+10]; struct node { ll cost,need; int S; }a[N]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } bool cmp(node a,node b) { return a.need<b.need; } int main() { // freopen("","r",stdin); // freopen("","w",stdout); // ios::sync_with_stdio(0); // cin.tie(0); n=read(),m=read(),scanf("%lld",&b); for(int i=1;i<=n;i++) { scanf("%lld%lld",&a[i].cost,&a[i].need); int num=read(); for(int j=1;j<=num;j++) { int x=read(); a[i].S=a[i].S|(1<<(x-1)); } } sort(a+1,a+n+1,cmp); for(int i=0;i<=1;i++) for(int j=0;j<(1<<m);j++) dp1[i][j]=dp2[i][j]=INF; dp1[0][0]=dp2[0][0]=0; for(int i=1;i<=n;i++) { for(int j=0;j<(1<<m);j++) { if(dp1[(i-1)%2][j]==INF) continue; dp1[i%2][j]=min(dp1[i%2][j],dp1[(i-1)%2][j]); dp2[i%2][j]=min(dp2[i%2][j],dp2[(i-1)%2][j]); if(dp1[i%2][j|a[i].S]>=dp2[(i-1)%2][j]+a[i].need*b+a[i].cost) { dp1[i%2][j|a[i].S]=dp2[(i-1)%2][j]+a[i].need*b+a[i].cost; dp2[i%2][j|a[i].S]=min(dp2[i%2][j|a[i].S],dp2[(i-1)%2][j]+a[i].cost); } dp1[(i-1)%2][j]=dp2[(i-1)%2][j]=INF; } // for(int j=0;j<(1<<m);j++) dp1[(i-1)%2][j]=dp2[(i-1)%2][j]=INF; } ll ans=INF; for(int i=1;i<=n;i++) ans=min(ans,dp1[n%2][(1<<m)-1]); if(ans==INF) puts("-1"); else printf("%lld",ans); return 0; }
C++14和C++17都会TLE，C++20能卡过去