POJ2441 Arrange the Bulls(状压DP)

题目是,有n头牛,每头牛都喜爱某几个草地,要把这n头牛分配给m个不同的它们喜爱的草地,问有几种分配方式。

  • dp[n][S]表示前n头牛分配完毕后占用的草地集合是S的方案数
  • dp[0][0]=1
  • dp[n][S]+=dp[n-1][S-x](x∈S且n喜爱x)

不过的状态这样空间开销太大了,事实上n这个维度的信息S就包含了,所以dp[S]即可。

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int d[<<];
bool map[][];
int main(){
int n,m,p,a;
scanf("%d%d",&n,&m);
for(int i=; i<n; ++i){
scanf("%d",&p);
while(p--){
scanf("%d",&a);
map[i][a-]=;
}
}
int res=;
d[]=;
for(int i=; i<(<<m); ++i){
int cnt=-;
for(int j=; j<m; ++j){
if((i>>j)&) ++cnt;
}
for(int j=; j<m; ++j){
if(((i>>j)&) && map[cnt][j]) d[i]+=d[i^(<<j)];
}
if(cnt==n-) res+=d[i];
}
printf("%d",res);
return ;
}
上一篇:matlab 曲线拟合小记


下一篇:耿丹CS16-2班第五次作业汇总