首页 > 代码库 > bzoj1231[Usaco2008 Nov]mixup2 混乱的奶牛*
bzoj1231[Usaco2008 Nov]mixup2 混乱的奶牛*
bzoj1231[Usaco2008 Nov]mixup2 混乱的奶牛
题意：
n头奶牛，每头有一个编号，求有多少种排列顺序使得相邻两头奶牛的编号差不超过k。n≤16。
题解：
状压dp。f[i][S]表示已选状态为S，上一个选的是i，满足要求的方案数，则f[i][S]=sum(f[j][S|j]),abs(num[i]-num[j])≤k。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define ll long long 6 #define INF 0x3fffffff 7 using namespace std; 8 9 ll dp[20][80000]; int n,k,s[20];10 ll dfs(int x,int y){11 if(!y)return 1; if(dp[x][y]!=-1)return dp[x][y]; dp[x][y]=0;12 inc(i,1,n)if((y&(1<<(i-1)))&&abs(s[i]-s[x])>k)dp[x][y]+=dfs(i,y^(1<<(i-1)));13 return dp[x][y];14 }15 int main(){16 scanf("%d%d",&n,&k); inc(i,1,n)scanf("%d",&s[i]); memset(dp,-1,sizeof(dp));17 s[0]=-INF; printf("%lld\n",dfs(0,(1<<n)-1)); return 0;18 }
20160908
bzoj1231[Usaco2008 Nov]mixup2 混乱的奶牛*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。