每头奶牛的编号都是唯一的,第i头奶牛的号子是Si

标题叙述

John家有N头奶牛,第i头奶牛的数码是Si,每头奶牛的数码都以绝无仅有的。那些奶牛近年来在闹特性,为表明不满的情怀,她们在挤奶的时候势要求排成混乱的人马。在2头混乱的队伍中,相邻奶牛的号码之差均超越K。比如当K = 1时,1, 3, 5, 2, 6,
4就是一支混乱的行伍, 而1, 3, 6, 5, 2,
4不是,因为6和八头差1。请数一数,有微微种队形是无规律的吧?

难题叙述

John家有N头奶牛,第i头奶牛的号码是Si,每头奶牛的数码都以唯一的。这个奶牛近期在闹天性,为发挥不满的心理,她们在挤奶的时候势须要排成混乱的武装。在四头混乱的队伍容貌中,相邻奶牛的编号之差均当先K。比如当K = 1时,1, 3, 5, 2, 6,
4就是一支混乱的枪杆子, 而1, 3, 6, 5, 2,
4不是,因为6和5只差1。请数一数,有稍许种队形是无规律的呢?

澳门真人网上娱乐网址,状压Dp

 见代码:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int n,K,end,a[16];
 6 long long dp[16][1<<16],ans;
 7 int main() {
 8     /*
 9         dp[i][j]在j状态中,队尾为第i头牛的方案数。
10         考虑在对位后加入新牛。无后效性。 
11     */
12     scanf("%d%d",&n,&K),end=1<<n;
13     for(int i=0;i<n;i++) scanf("%d",&a[i]);
14     for(int i=0;i<n;i++) dp[i][1<<i]=1;
15     for(int i=0;i<end;i++) {//枚举状态 
16         for(int j=0;j<n;j++) if(i&(1<<j))//枚举以那头牛为队尾 
17         for(int k=0;k<n;k++) if(!(i&(1<<k)) && abs(a[j]-a[k])>K)//枚举新添入哪头牛 
18         dp[k][i|(1<<k)]+=dp[j][i];
19     }
20     for(int i=0;i<n;i++) ans+=dp[i][end-1];//全牛 
21     printf("%lld\n",ans);
22     return 0;
23 }

实则就是把搜索中的状态用很有利的款型保留了,以巡回的样式落到实处

状压Dp

 见代码:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int n,K,end,a[16];
 6 long long dp[16][1<<16],ans;
 7 int main() {
 8     /*
 9         dp[i][j]在j状态中,队尾为第i头牛的方案数。
10         考虑在对位后加入新牛。无后效性。 
11     */
12     scanf("%d%d",&n,&K),end=1<<n;
13     for(int i=0;i<n;i++) scanf("%d",&a[i]);
14     for(int i=0;i<n;i++) dp[i][1<<i]=1;
15     for(int i=0;i<end;i++) {//枚举状态 
16         for(int j=0;j<n;j++) if(i&(1<<j))//枚举以那头牛为队尾 
17         for(int k=0;k<n;k++) if(!(i&(1<<k)) && abs(a[j]-a[k])>K)//枚举新添入哪头牛 
18         dp[k][i|(1<<k)]+=dp[j][i];
19     }
20     for(int i=0;i<n;i++) ans+=dp[i][end-1];//全牛 
21     printf("%lld\n",ans);
22     return 0;
23 }

骨子里就是把搜索中的状态用很有益于的款型保留了,以巡回的样式完成