dp[i][j] 到第i个物品 状态为 j 的二进制串 能得到的最大价值
#include<cstdio> #include<cstring> #include<map> #include<iostream> #include<algorithm> #include<math.h> #include<map> #include<queue> #include<set> #include<vector> using namespace std; #define inf 1000000007 #define ll long long #define MAXN 1010 int dp[MAXN][(1<<10)+10]; int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); int ed=1<<m; for(int i=0;i<=n;i++) { for(int j=0;j<=ed;j++) dp[i][j]=-inf; } dp[0][0]=0; int d=ed-1; for(int i=1;i<=n;i++) { int w,k; scanf("%d%d",&w,&k); int a=0; for(int j=1;j<=k;j++) { int b; scanf("%d",&b); b--; a=a+(1<<b); } for(int j=0;j<=d;j++) { dp[i][j^a]=max(dp[i-1][j]+w,dp[i][j^a]); dp[i][j]=max(dp[i-1][j],dp[i][j]); } } int mx=0; mx=max(mx,dp[n][d]); cout<<mx<<endl; } return 0; }
#include<cstdio> #include<cstring> #include<map> #include<iostream> #include<algorithm> #include<math.h> #include<map> #include<queue> #include<set> #include<vector> using namespace std; #define inf 1000000007 #define ll long long #define MAXN 1010 int dp[MAXN][(1<<10)+10]; int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); int ed=1<<m; for(int i=0;i<=n;i++) { for(int j=0;j<=ed;j++) dp[i][j]=-inf; } dp[0][0]=0; int d=ed-1; for(int i=1;i<=n;i++) { int w,k; scanf("%d%d",&w,&k); int a=0; for(int j=1;j<=k;j++) { int b; scanf("%d",&b); b--; a=a+(1<<b); } for(int j=0;j<=d;j++) { dp[i][j^a]=max(dp[i-1][j]+w,dp[i][j^a]); dp[i][j^a]=max(dp[i-1][j^a],dp[i][j^a]); } } int mx=0; mx=max(mx,dp[n][d]); cout<<mx<<endl; } return