状压DP之Mixed Up Cows G

题目

传送们

大意

约翰家有N头奶牛，第i头奶牛的编号是Si，每头奶牛的编号都是唯一的。这些奶牛最近 在闹脾气，为表达不满的情绪，她们在挤奶的时候一定要排成混乱的队伍。在一只混乱的队 伍中，相邻奶牛的编号之差均超过K。比如当K = 1时，1, 3, 5, 2, 6, 4就是一支混乱的队伍， 而1, 3, 6, 5, 2, 4不是，因为6和5只差1。请数一数，有多少种队形是混乱的呢？

思路

定义f[i][j]表示最后一头牛是i且前i头牛的状态，
f[i][1<<(i-1)]=1,当最后一头牛是i，且只有i一头牛时方案数是1

• 接下来我们进行dp
  首先枚举状态i，然后枚举最后一头牛j，如果i&(1<<(j-1))==0，即为状态中不包括最后一头牛，肯定不合法，然后枚举最后加上的一头牛k，i & (1<<(k-1)）！=0时，已包括k，所以不需要转移，abs(a[k]-a[j])<=k1为有序状态，不合法，不能进行转移，处理完不合法的状态后，可得状态转移方程

f[k][i|(1<<(k-1))]+=f[j][i];

将前面的方案数累加到以k结尾，状态为i|(1<<(k-1))的结果中去，
最后累加到ans即可（记得开long long）

附上代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
long long f[20][(1<<16)+10];
int a[20];
int n,k1;
int main(){
	scanf("%d%d",&n,&k1);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		f[i][1<<(i-1)]=1;
	}
	int lim=1<<n;
	for(int i=0;i<lim;i++){
		for(int j=1;j<=n;j++){
			if(i&(1<<(j-1))==0)continue;
			for(int k=1;k<=n;k++){
				if((i & (1<<(k-1))) || abs(a[k]-a[j])<=k1)continue;
				f[k][i|(1<<(k-1))]+=f[j][i];
			}
		}
	}
	long long ans=0;
	for(int i=1;i<=n;i++){
		ans+=f[i][(1<<n)-1];
	}
	cout<<ans<<endl;
}

状压DP之Mixed Up Cows G

原文：https://www.cnblogs.com/soda-ma/p/13232850.html