[BZOJ 1231][Usaco2008 Nov]mixup2 混乱的奶牛：状压DP

本文主要是介绍[BZOJ 1231][Usaco2008 Nov]mixup2 混乱的奶牛：状压DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击这里查看原题

f[i][j]表示状态为i，以奶牛j结尾的情况数

/*
User:Small
Language:C++
Problem No.:1231
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
const int M=(1<<16)+5;
int a[20],n,t;
ll f[M][20],ans; 
int main(){freopen("data.in","r",stdin);//scanf("%d%d",&n,&t);for(int i=0;i<n;i++){scanf("%d",&a[i]);f[1<<i][i]=1;}for(int i=0;i<(1<<n);i++)for(int j=0;j<n;j++){if((i&(1<<j))==0) continue;for(int k=0;k<n;k++)if((i&(1<<k))==0&&abs(a[j]-a[k])>t) f[i|(1<<k)][k]+=f[i][j];}for(int i=0;i<n;i++) ans+=f[(1<<n)-1][i];printf("%lld\n",ans);return 0;
}

这篇关于[BZOJ 1231][Usaco2008 Nov]mixup2 混乱的奶牛：状压DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---