4) 便是一支混乱的军事,混乱的奶牛

题材叙述

John有 N 头奶牛,第 i 头奶牛的数码是 S i
,每头奶牛的编号都不比。那几个奶牛近来在闹性格,

为发挥不满的心思,她们在排队的时候肯定要排成混乱的军旅。假设二头阵容里存有职位紧邻的奶牛

的数码之差都高于 K,那么那就是三只混乱的枪杆子,在那之中 K
是一个加以的整数。比如说,当 K = 2

时,种类 (1,3,5,2,6,4) 正是一支混乱的部队,而 (1,3,6,5,2,4) 不是,因为 6
和 5 只差 1,不够混

乱。请问,那 N 头奶牛能够排成多少种混乱的队形呢?

[Usaco2008 Nov]mixup2 混乱的奶牛

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1204  Solved: 698
[Submit][Status][Discuss]

输入

• 第三行:四个整数 N 和 K,4 ≤ N ≤ 16, 1 ≤ K ≤ 3400

• 第三行到第 N + 1 行:第 i + 1 行有三个整数 S i ,1 ≤ S i ≤ 2四千

Description

散乱的奶牛 [Don Piele, 2007] Farmer
约翰的N(4 <= N <= 16)头奶牛中的每三头都有三个唯一的编号S_i (1
<= S_i <= 25,000). 奶牛为她们的号子感到骄傲,
所以每3只奶牛都把他的编号刻在三个金牌上,
并且把金牌挂在他们宽大的脖子上.
奶牛们对在挤奶的时候被排成一支”混乱”的人马11分反感.
就算1位马里随意四头相邻的奶牛的号码相差当先K (1 <= K <= 3400),
它就被喻为是乱套的. 比如说,当N = 6, K = 1时, 1, 3, 5, 2, 6, 4
正是一支”混乱”的军旅, 不过 1, 3, 6, 5, 2, 4 不是(因为5和五只相差1). 那么,
有多少种能够使奶牛排成”混乱”的武装的方案吗?

输出

• 单个整数:表示混乱队伍容貌的数额

Input

* 第 1 行: 用空格隔离的七个整数N和K

* 第 2..N+1 行:
第i+1行包罗了三个用来代表第i头奶牛的号子的整数: S_i

样例输入

4 1 3 4 2 1

Output

第 1 行: 唯有1个整数,
表示有些许种能够使奶牛排成”混乱”的部队的方案. 答案保障是
二个在64位范围内的整数.

样例输出

2

Sample Input

4 1
3
4
2
1

提示

二种排法是 3,1,4,2 和 2,4,1,3

 

题解:

乱搞搞对的,不知对不对,看到n<=16
于是想到状压

F[i][j]
表示以i结尾,状态为j的方案数

接下来便是一旦满足S[i]-S[k]>p 就F[i][j]+=F[k][j-(1<<(i-1))]

注意开long
long

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int N=17;
 7 int a[N];long long F[N][1<<N];
 8 int main()
 9 {
10     int n,p;
11     scanf("%d%d",&n,&p);
12     for(int i=1;i<=n;i++)scanf("%d",&a[i]),F[i][(1<<(i-1))]=1;
13     sort(a+1,a+n+1);
14     int m=(1<<n)-1;
15     for(int j=1;j<=m;j++)
16     {
17         for(int i=1;i<=n;i++)
18         {
19             if(!(j&(1<<(i-1))))continue;
20             for(int k=1;k<=n;k++)
21             {
22                 if(abs(a[i]-a[k])<=p)continue;
23                 if(!(j&(1<<(k-1))))continue;
24                 F[i][j]+=F[k][j-(1<<(i-1))];
25             }
26         }
27     }
28     long long ans=0;
29     for(int i=1;i<=n;i++)ans+=F[i][m];
30     printf("%lld",ans);
31     return 0;
32 }

Sample Output

2

输出解释:

三种艺术分别是:
3 1 4 2
2 4 1 3

题解:设f[i][j]代表以第i个奶牛结尾,奶牛的取舍景况为j的方案数。

转移方程也比较不难f[k][(1<<(k-1))|j]+=f[i][j];(abs(a[k]-a[i])>K,(1<<(k-1))|j!=j,(1<<(i-1))&j!=0)

初始令f[i][1<<i]=1即可。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring> 
 5 using namespace std;
 6 int n,kk,p[20],a[20],maxx;
 7 long long f[20][1<<16],ans;
 8 int main(){
 9   scanf("%d%d",&n,&kk);maxx=(1<<n)-1;
10   for(int i=1;i<=n;i++){scanf("%d",&a[i]);p[i]=1<<(i-1);}
11   for (int i=1;i<=n;i++)f[i][p[i]]=1;
12   for (int i=0;i<=maxx;i++)
13    for (int j=1;j<=n;j++)
14     if (p[j]&i)
15      for (int k=1;k<=n;k++)
16        if ((p[k]|i)!=i&&abs(a[k]-a[j])>kk) f[k][p[k]|i]+=f[j][i];
17   for (int i=1;i<=n;i++) ans+=f[i][maxx];
18   cout<<ans<<endl;
19 }