题目描述

约翰家有N头奶牛,第i头奶牛的编号是Si,每头奶牛的编号都是唯一的。这些奶牛最近 在闹脾气,为表达不满的情绪,她们在挤奶的时候一定要排成混乱的队伍。在一只混乱的队 伍中,相邻奶牛的编号之差均超过K。比如当K = 1时,1, 3, 5, 2, 6, 4就是一支混乱的队伍, 而1, 3, 6, 5, 2, 4不是,因为6和5只差1。请数一数,有多少种队形是混乱的呢?

输入输出格式

输入格式:
  • 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


状压DP,首先考虑一下f[i]表示i状态方案数
发现不知道他前面那头牛是什么
那f[i][j]表示i状态下末尾的牛是j
这样式子就很好写出来了
$$ f[i|1<<(z-1)][z]+=f[i][j] $$
其中z表示还没有进去的奶牛


说点什么

avatar
  Subscribe  
提醒