间隔排列

题目：

【题意描述】

有2N个木块，每个木块标上1到N的自然数中的一个，每个数字会出现在两个木块上。把这些木块排成一排，要求是：标号为i的两个木块之间要间隔i个其它木块。比如说N=3的情况，下面就是一个可行的排列：3，1，2，1，3，2。编程实现，对给定的N，求出一个可行排列。

【输入格式】

输入只有一行，给出一个数字N,N<=40

【输出格式】

输出一个满足题意的排列,任两个数字间用一个空格隔开,无解则输出”No Solution”

【样例输入】

3

【样例输出】

3 1 2 1 3 2

这道题，因为题目没读懂卡了我半天，在我心中，这道题应是这个样子的：

但在其他人的眼中，这道题是这样的：

3 1 2 1 3 2

好吧，少数服从多数，我就按他们的思路来吧。

我的思路好像似乎有点问题

我们只需要枚举放到那个位置，当深度达到n时，ans++即可。

我最开始为什么没读懂题？

脑回路惊奇

好了好了，我们进入正题，代码如下：

#include <bits/stdc++.h>
using namespace std;

int vis[1010],ans,n;

void dfs (int dep){
	if(dep>n){
		ans++;
		return;
		
	}
	
	for (int i=1;i<=2*n-dep-1;i++){
		if(!vis[i]&&!vis[i+dep+1]){
			vis[i]=1;
			vis[i+dep+1]=1;
			dfs(dep+1);
			vis[i]=0;
			vis[dep+i+1]=0;
		}
	}
	
}

int main(){
	cin>>n;
	dfs(1);
	cout<<ans;
	return 0;
}