输入格式,每头奶牛的号码都是绝无仅有的

标题叙述

Each of Farmer John’s N (4 <= N <= 16) cows has a unique serial
number S_i (1 <= S_i <= 25,000). The cows are so proud of it
that each one now wears her number in a gangsta manner engraved in large
letters on a gold plate hung around her ample bovine neck.

Gangsta cows are rebellious and line up to be milked in an order called
‘Mixed Up’. A cow order is ‘Mixed Up’ if the sequence of serial numbers
formed by their milking line is such that the serial numbers of every
pair of consecutive cows in line differs by more than K (1 <= K <=
3400). For example, if N = 6 and K = 1 then 1, 3, 5, 2, 6, 4 is a ‘Mixed
Up’ lineup but 1, 3, 6, 5, 2, 4 is not (since the consecutive numbers 5
and 6 differ by 1).

How many different ways can N cows be Mixed Up?

For your first 10 submissions, you will be provided with the results of
running your program on a part of the actual test data.

POINTS: 200

John家有N头奶牛,第i头奶牛的编号是Si,每头奶牛的号码都以唯一的。那么些奶牛近来在闹脾性,为发挥不满的心气,她们在挤奶的时候料定要排成混乱的武力。在多头混乱的队
5中,相邻奶牛的号码之差均当先K。比方当K = 壹时,1, 三, 5, 贰, 陆,
四就是壹支混乱的军队, 而一, 三, 6, 5, 二,
4不是,因为陆和九头差一。请数一数,有个别许种队形是乱套的吧?

P2915 [USACO08NOV]奶牛混合起来Mixed Up Cows

输入输出格式

输入格式:

 

  • Line 1: Two space-separated integers: N and K

  • Lines 2..N+1: Line i+1 contains a single integer that is the serial
    number of cow i: S_i

 

出口格式:

 

  • Line 1: A single integer that is the number of ways that N cows can
    be ‘Mixed Up’. The answer is guaranteed to fit in a 64 bit integer.

 

难点叙述

Each of Farmer John’s N (4 <= N <= 16) cows has a unique serial
number S_i (1 <= S_i <= 25,000). The cows are so proud of it
that each one now wears her number in a gangsta manner engraved in large
letters on a gold plate hung around her ample bovine neck.

Gangsta cows are rebellious and line up to be milked in an order called
‘Mixed Up’. A cow order is ‘Mixed Up’ if the sequence of serial numbers
formed by their milking line is such that the serial numbers of every
pair of consecutive cows in line differs by more than K (1 <= K <=
3400). For example, if N = 6 and K = 1 then 1, 3, 5, 2, 6, 4 is a ‘Mixed
Up’ lineup but 1, 3, 6, 5, 2, 4 is not (since the consecutive numbers 5
and 6 differ by 1).

How many different ways can N cows be Mixed Up?

For your first 10 submissions, you will be provided with the results of
running your program on a part of the actual test data.

POINTS: 200

John家有N头奶牛,第i头奶牛的数码是Si,每头奶牛的数码都以绝无仅有的。这个奶牛最近在闹特性,为表达不满的心怀,她们在挤奶的时候势供给排成混乱的武装部队。在二头混乱的队
伍中,相邻奶牛的号码之差均当先K。比方当K = 一时,一, 3, 5, 2, 陆,
肆正是1支混乱的队5, 而一, 三, 6, 5, 2,
四不是,因为六和玖头差一。请数1数,有微微种队形是无规律的吧?

输入输出样例

输入样例#1:

4 1 
3 
4 
2 
1 

输出样例#1:

2 

输入输出格式

输入格式:

 

  • Line 1: Two space-separated integers: N and K

  • Lines 2..N+1: Line i+1 contains a single integer that is the serial
    number of cow i: S_i

 

出口格式:

 

  • Line 1: A single integer that is the number of ways that N cows can
    be ‘Mixed Up’. The answer is guaranteed to fit in a 64 bit integer.

 

说明

The 2 possible Mixed Up arrangements are:

3 1 4 2

2 4 1 3

 

变量名争辨调了许久,,,

状压dp。

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

 

输入输出样例

输入样例#1:

4 1 
3 
4 
2 
1 

输出样例#1:

2 

说明

The 2 possible Mixed Up arrangements are:

3 1 4 2

2 4 1 3

图片 1图片 2

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#define maxn 20
using namespace std;
int n,k,a[maxn],ans;
bool vis[maxn];
void dfs(int cnt,int pre){
    if(cnt==n){ans++;return;}
    for(int i=1;i<=n;i++){
        if(!vis[i]&&abs(a[i]-pre)>k){
            vis[i]=1;
            dfs(cnt+1,a[i]);
            vis[i]=0;
        }
    }
}
int main(){
    freopen("Cola.txt","r",stdin);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    dfs(0,-4000);
    printf("%d",ans);
}

70分 暴力

图片 3图片 4

/*
    记忆化搜索,f[sta][i]表示选了的牛的集合为sta,且最后一个牛是i的混乱序列方案数 
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#define maxn 20
#ifdef WIM32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
int n,k,a[maxn],ans;
bool vis[maxn];
long long f[1<<16][20];
long long dfs(int sta,int cnt,int pre){
    if(cnt==n){return f[sta][pre]=1;}
    if(f[sta][pre]!=-1)return f[sta][pre];
    long long res=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]&&abs(a[i]-a[pre])>k){
            vis[i]=1;
            res+=dfs(sta+(1<<(i-1)),cnt+1,i);
            vis[i]=0;
        }
    }
    f[sta][pre]=res;
    return res;
}
int main(){
    memset(f,-1,sizeof(f));
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    a[0]=-4000;
    dfs(0,0,0);
    printf(LL,f[0][0]);
}

玖16分 纪念化寻找

图片 5图片 6

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#ifdef WIN32
#define LL "%I64d"
#else 
#define LL "%lld"
#endif
using namespace std;
int n,k,a[20];
long long f[1<<16][20];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)f[(1<<(i-1))][i]=1;
    for(int sta=2;sta<(1<<n);sta++){
        for(int i=1;i<=n;i++){
            if(sta&(1<<(i-1))){
                for(int j=1;j<=n;j++){
                    if(abs(a[j]-a[i])>k)f[sta][i]+=f[sta^(1<<(i-1))][j];
                }
            }
        }
    }
    long long ans=0;
    for(int i=1;i<=n;i++)ans+=f[(1<<n)-1][i];
    printf(LL,ans);
}

100分 递推