k=22左右似乎只能集合并卷积卡常了

正反dp是个玄学……

k>=0 不是>=1

回复楼上，确实可以

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<ctime>
#include<cmath>
#include<map>
#include<set>
#define MAXX 501
using namespace std;
int n,k,d,ans,f[MAXX][16*16*16*16+1],len[MAXX],p[MAXX][16];
void init(){
scanf("%d%d%d",&n,&d,&k);
for(int i=1;i<=n;++i){
scanf("%d",&len[i]);
for(int j=1;j<=len[i];++j)scanf("%d",&p[i][j]);
}
}
bool check(int j){
int num=0;
while(j){
num+=(j&1);
j>>=1;
}
if(num>k)return 0;
return 1;
}
void findanswer(){
for(int i=1;i<=n;++i){
for(int j=0;j<=(1<<d);++j){
if(!check(j))continue;
int jj=j;
for(int h=1;h<=len[i];++h)jj=jj|(1<<(p[i][h]-1));
if(check(jj))f[i][jj]=max(f[i-1][jj],f[i-1][j]+1);//挤或不挤
f[i][j]=max(f[i][j],f[i-1][j]);
ans=max(ans,max(f[i][j],f[i][jj]));
}
}
printf("%d",ans);
return;
}
int main(){
freopen("disease.in","r",stdin);
freopen("disease.out","w",stdout);
init();
findanswer();
return 0;
}

回应楼上↑：这就是只状压，不dp的写法 =-=

此题可以只有状压，没有dp。

f[i]代表疾病状态为i的情况下最多有多少只羊

(震惊的)状压