题目描述
约翰家有N头奶牛，第i头奶牛的编号是Si，每头奶牛的编号都是唯一的。这些奶牛最近 在闹脾气，为表达不满的情绪，她们在挤奶的时候一定要排成混乱的队伍。在一只混乱的队 伍中，相邻奶牛的编号之差均超过K。比如当K = 1时，1, 3, 5, 2, 6, 4就是一支混乱的队伍， 而1, 3, 6, 5, 2, 4不是，因为6和5只差1。请数一数，有多少种队形是混乱的呢？
状压Dp
见代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
];
][<<],ans;
int main() {
/*
dp[i][j]在j状态中，队尾为第i头牛的方案数。
考虑在对位后加入新牛。无后效性。
*/
scanf(<<n;
;i<n;i++) scanf("%d",&a[i]);
;i<n;i++) dp[i][<<i]=;
;i<end;i++) {//枚举状态
;j<n;j++) <<j))//枚举以那头牛为队尾
;k<n;k++) <<k)) && abs(a[j]-a[k])>K)//枚举新添入哪头牛
dp[k][i|(<<k)]+=dp[j][i];
}
;i<n;i++) ans+=dp[i][end-];//全牛
printf("%lld\n",ans);
;
}
其实就是把搜索中的状态用很方便的形式保存了，以循环的形式实现