Farmer John is calling his N (1 <= N <= 10) cows to a very important meeting at a round table.
The cows are rather anxious about this meeting since they want to put forth their very best image. To make the table arrangement attractive, they want to ensure that any two cows sitting next to each other to differ in height by no more than K (1 <= K <= 1,000,000) millimeters (cow i has integer height H_i (1 <= H_i <= 1,000,000) millimeters).
Help calculate the number of ways the cows can sit down at the round table such that no two adjacent cows differ in height by more than K millimeters. Two ways are different if there is at least one cow with a different cow to its left in each arrangement.
The answer is guaranteed to fit in a 32-bit signed integer.
Input
* Line 1: Two space-separated integers, N and K
* Lines 2..N+1: Line i+1 contains height H_i
Output
* Line 1: The number of ways that the cows can sit down at the round table such that two adjacent cows do not differ in height by more than K millimeters.
Sample Input
4 10
2
16
6
10
Sample Output
2
Hint
INPUT DETAILS:
There are 4 cows, with heights 2, 16, 6, and 10. Two cows whose heights differ by more than 10 do not want to sit next to each other.
OUTPUT DETAILS:
Clearly the cows with heights 2 and 16 must be opposite each other, so there are 2 ways to place the cows of height 6 and 10.
解题思路：
N值不大(<10)，可以采用枚举，搜索所有可能的情况。
注意：
为了避免出现重复的情况，固定第一个人的位置在0号位置，它的位置是不变的。
#include
#include
int height[11], table[11], choosed[11];
int N, K;
long long count;
void recursion(int start, int cows)
{
int i, left_abs, right_abs;
if (0 == start) /* 刚开始，需要跳过下面的检查，直接插入下一个 */
goto loop;
/* 如果和左边的一个差值大于K，则结束这个组合的搜索 */
left_abs = abs(table[start] - table[start - 1]);
/* judge left satisfy? */
if (left_abs > K)
return;
/* judge right satisfy? */
/* 最后一个，除了需要检查左边之外，还要检查右边 */
if (start == cows - 1)
{
right_abs = abs(table[start] - table[0]);
if (right_abs <= K)
{
/* 满足一种组合情况，计数加一 */
count++;
/*
int j;
for (j=0 ; j
printf("\n");
*/
}
return ;
}
/* 在这里实现循环中的递归，搜索所有情况 */
loop:
for (i=1; i
if (1 == choosed[i]) /* 判断这个cow是否被选择过 */
continue;
table[start + 1] = height[i];
choosed[i] = 1; /* 选择之 */
recursion(start + 1, cows);
choosed[i] = 0; /* OK，恢复之前的状态 */
}
}
int main(int argc, char *argv[])
{
int i;
scanf("%d %d", &N, &K);
for (i=0 ; i
table[0] = height[0];
count = 0;
choosed[0] = 1;
recursion(0, N);
if (1 == N)
count = 1;
printf("%lld\n", count);
}