P83901

混乱的奶牛

难度 6 级 动态规划入门 状态压缩
讨论 统计 6通过 11提交 54.5%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

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

输入

第1行:两个空格分隔的整数:N和K

第2..N+1行:第i+1行包含一个整数,即奶牛i:S_i的序列号

输出

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
输出
2

提示

The 2 possible Mixed Up arrangements are:

3 1 4 2

2 4 1 3

来源

USACO

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交