题意:约翰家有\(N(4<=N<=16)\)头奶牛，第\(i\)头奶牛的编号是\(a_i\)，每头奶牛的编号都是唯一的.这些奶牛最近 在闹脾气，为表达不满的情绪，她们在挤奶的时候一定要排成混乱的队伍。在一只混乱的队 伍中，相邻奶牛的编号之差均超过\(m\).比如当\(m = 1\)时，\(1, 3, 5, 2, 6, 4\)就是一支混乱的队伍， 而\(1, 3, 6, 5, 2, 4\)不是，因为\(6\)和\(5\)只差\(1\)请数一数，有多少种队形是混乱的呢？
分析:首先,\(n<=16\),用每一个二进制位表示这头奶牛当前有没有被选是很明显的吧,继而想到状压\(DP\).已经有一维表示当前选的奶牛的集合,发现想要转移必须要知道当前最后选的奶牛是谁?所以设\(f[i][j]\)表示当前最后选了第\(i\)头牛,已经选的奶牛的集合为\(j\)时的方案数.
\(f[i][j]=f[k][j\)^\((1<<(i-1))]\),其中\(abs(a[k]-a[i])>m\).
然后我就意难平了.详情请见代码.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
int a[20];ll ans,f[20][100005];//记得开long long
int main(){
int n=read(),m=read();
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=n;++i)f[i][1<<(i-1)]=1;
/*for(int i=1;i<=n;++i){
for(int j=1;j<(1<<n);++j){
if(j&(1<<(i-1))){
for(int k=1;k<=n;++k){
if(k==i||abs(a[k]-a[i])<=m)continue;
if(j&(1<<(k-1)))f[i][j]+=f[k][j^(1<<(i-1))];
}
}
}
}*/
//上面是我刚开始写的代码,搞了一个多小时,样例都过不去
//然后去看题解,就换一个i,j的枚举顺序就行了,不多说了,菜是原罪.
//然后仔细想想,一般状压DP,都是先枚举的集合状态是吧.
//这样才能保证对于一个集合j,所有能够转移到它的集合j'都已经被更新完了
//就是说上面那种写法,更新f[i][j]+=f[k][j^(1<<(i-1))]的时候
//当k>i时,f[k][j^(1<<(i-1))]是还没有被更新的.
for(int j=1;j<(1<<n);++j){
for(int i=1;i<=n;++i){
if(j&(1<<(i-1))){
for(int k=1;k<=n;++k){
if(abs(a[k]-a[i])<=m)continue;
if(j&(1<<(k-1)))f[i][j]+=f[k][j^(1<<(i-1))];
}
}
}
}
for(int i=1;i<=n;++i)ans+=f[i][(1<<n)-1];
printf("%lld\n",ans);
return 0;
}