Liserious最近迷上了密室逃脱，他总是在跪求他的小伙伴和他一起去玩各种各样的密室逃脱。
有一天他们遇到了一家非常复杂的密逃，为了获得其中一个关键道具，他们需要先站成一列，李希尔瑞斯的小伙伴们来自N个小组（比如一姐带领的“EEEat”；芳姐带领的“Doctooor”小组；51isoft带领的“Weeaaak”小组；力儿妹妹带领的“Mahhhjong”小组；龚犇带领的“Life Winnerrr”小组）。
现在每个人对自己的位置都有一个要求，要么他是他所在小组的队列里的第一个，要么他与他同一小组的前一个人的距离恰好为K。
输入以EOF结束。
每组数据的第一行为一个整数N，表示小组的数量。
接下来N行，每行第一个整数M(M <= 5)，表示这个小组的人数，接下来M个数，分别表示这M个人要求距离前一个同组的小伙伴的距离。
输入保证小伙伴的总数不超过20。
对于每组数据，输出一个整数，表示总的排列的方案数。
思路：
这个题和这道题基本是一个套路：http://blog.csdn.net/mengxiang000000/article/details/60767512 我们知道，当n大的时候，M平均起来肯定小，也就是说对于每组的人的摆放的情况就会少很多，所以我们每次考虑两个组的合并。 设定Dp【i】表示已经排列出来状态为i的情况的方案数。 那么有：Dp【i】+=preDp【j】，这里i=j|X,这里X表示的是当前组成员的某种插入队列的方式。我们知道，当n大的时候，M平均起来肯定小，所以前期的情况数肯定灰常少， 所以我们只要注意常数就可以了。理论上是可以找到峰值操作次数的。 那么我们每一次将之前的排放方式和当前组的排放方式去合并Dp即可，注意常数。
Ac代码：
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<queue> #include<vector> #include<map> using namespace std; #define ll long long int int tot,n; int Dist[25][25]; int num[25]; int p[25]; ll dp[(1<<21)]; ll predp[(1<<21)]; vector<int>mp[25]; void Slove() { vector<int>pre,zhongjie; memset(dp,0,sizeof(dp)); memset(predp,0,sizeof(predp)); pre.push_back(0);predp[0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<mp[i].size();j++) { int tmpi=mp[i][j]; for(int k=0;k<pre.size();k++) { int tmppre=pre[k]; if((tmppre&tmpi)>0)continue; if(dp[tmppre+tmpi]==0)zhongjie.push_back(tmppre+tmpi); dp[tmppre+tmpi]+=predp[tmppre]; } } pre.clear(); for(int j=0;j<zhongjie.size();j++) { predp[zhongjie[j]]+=dp[zhongjie[j]]; dp[zhongjie[j]]=0; pre.push_back(zhongjie[j]); } zhongjie.clear(); } printf("%lld\n",predp[(1<<tot)-1]); } int main() { while(~scanf("%d",&n)) { tot=0; for(int i=1;i<=24;i++)mp[i].clear(); for(int i=1;i<=n;i++) { int ki,cnt=1; scanf("%d",&ki); tot+=ki; num[i]=ki; for(int j=1;j<=ki;j++)scanf("%d",&Dist[i][j]); } for(int i=1;i<=n;i++) { int cnt=1; for(int j=1;j<=num[i];j++)p[j]=j,cnt*=j; while(cnt--) { next_permutation(p+1,p+1+num[i]); for(int pos=tot-1;pos>=0;pos--) { int tmp=0; int tmppos=pos; for(int j=1;j<=num[i];j++) { if(j>1)tmppos-=Dist[i][p[j-1]]; tmp+=(1<<tmppos); } if(tmppos<0)continue; mp[i].push_back(tmp); } } } Slove(); } }
