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

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

题目描述

Each of Farmer John’s \(N (4 \leq N \leq 16)\) cows has a unique serial number \(S_i (1 \leq S_i \leq 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 \leq K \leq 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?

 

输入输出格式

输入格式

* 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.

 

输入输出样例

输入样例#1

4 1 
3 
4 
2 
1 

 

输出样例#1

2 

 

说明

The \(2\) possible Mixed Up arrangements are:

\(3 1 4 2\)

\(2 4 1 3\)

 

思路

简单的状压DP,用\(f[i][S]\)表示以第\(i\)头奶牛结尾,当前队内奶牛集合为\(S\)的方案数

 

代码

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int N, K, s[17];
long long f[17][1<<16], ans;

int main(){
	scanf("%d%d", &N, &K);
	for(int i=1; i<=N; i++){
		scanf("%d", &s[i]);
		f[i][1<<(i-1)]=1;
	}
	for(int i=0; i<(1<<N); i++)
		for(int j=1; j<=N; j++){
			if(((1<<(j-1))&i)==0)	continue;
			for(int k=1; k<=N; k++){
				if(((1<<(k-1))&i)!=0 || abs(s[j]-s[k])<=K)	continue;
				f[k][i|(1<<(k-1))]+=f[j][i];
			}
		}
	for(int i=1; i<=N; i++)
		ans+=f[i][(1<<N)-1];
	printf("%lld", ans);
	return 0;
}

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注