这个题的dp真的恶心。首先，一开始我以为是一道数论题，但是组合数和这个题没啥关系。dp方程巨麻烦，状态是dp[i][j][0/1]，代表i位连了j个，上一位是否连着。然后开始转移，证明如下：
我们先来分析i-1,i相邻，也就是f[i][j][1]怎么推。
对于i,i-1,i-2，有这几种关系，
本来i-1与i-2相邻，将i插入两者中，拆了一对(i-1,i-2),又形成了一对(i-1,i)，这样方案来源于f[i-1][j][1]。
本来i-1与i-2相邻，将i插入与i-1相邻却不被i-1与i-2夹着，多形成了一对(i-1,i)，这样方案来源于f[i-1][j-1][1]。
本来i-1与i-2不相邻，将i插入与i-1相邻，形成了一对(i-1,i)，这样方案来源于f[i-1][j-1][1]，由于i-1的左右够可以插，方案就乘2。
这样f[i][j][1]=f[i−1][j−1][1]+f[i−1][j][1]+f[i−1][j−1][0]∗2
关于i-1,i不相邻，也就是f[i][j][0]怎么推
本来i-1与i-2相邻，将i插入j对相邻的数的任意一对，这样就破坏了一对，这样方案来源于f[i-1][j+1][1]，有（j+1-1）种位置可以选(i-1与i-2那对不能拆，因为插入又会形成新的)。
本来i-1与i-2不相邻，将i插入j对相邻的数的任意一对，这样就破坏了一对，这样方案来源于f[i-1][j+1][0]，有（j+1）种位置可以选。
又可能i不去拆开相邻的数，就可以来源于
f[i-1][j][1]*(i-j-1)(可以插入i-1与i-2，不改变对数) 或 f[i-1][j][0]*(i-j-2)
综合
f[i][j][0]=f[i−1][j+1][1]∗j+f[i−1][j+1][0]∗(j+1)+f[i−1][j][1]∗(i−j−1)+f[i−1][j][0]∗(i−j−2)
很难推的题呀。。。。
题干：
Description
n 个沙茶，被编号 ~n。排完队之后，每个沙茶希望，自己的相邻的两
人只要无一个人的编号和自己的编号相差为 （+ 或-）就行；
现在想知道，存在多少方案满足沙茶们如此不苛刻的条件。 Input
只有一行且为用空格隔开的一个正整数 N，其中 %的数据满足 ≤N ≤ ; Output
一个非负整数，表示方案数对 取模。 Sample Input Sample Output 样例解释：有两种方案 和
HINT Source
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
#define duke(i,a,n) for(int i = a;i <= n;i++)
#define lv(i,a,n) for(int i = a;i >= n;i--)
#define clean(a) memset(a,0,sizeof(a))
const int INF = << ;
const int mod = ;
typedef long long ll;
typedef double db;
template <class T>
void read(T &x)
{
char c;
bool op = ;
while(c = getchar(), c < '' || c > '')
if(c == '-') op = ;
x = c - '';
while(c = getchar(), c >= '' && c <= '')
x = x * + c - '';
if(op) x = -x;
}
template <class T>
void write(T x)
{
if(x < ) putchar('-'), x = -x;
if(x >= ) write(x / );
putchar('' + x % );
}
ll dp[][][];
int main()
{
int n;
read(n);
dp[][][] = ;
duke(i,,n)
{
duke(j,,i)
{
dp[i][j][] = (dp[i - ][j - ][] + dp[i - ][j][] + dp[i - ][j - ][] * ) % mod;
dp[i][j][] = (dp[i - ][j][] * (i - j - ) + dp[i - ][j + ][] * j + dp[i - ][j + ][] * (j + ) + dp[i - ][j][] * (i - j - )) % mod;
}
}
printf("%lld\n",dp[n][][]);
return ;
}