题意：
锁上有n个槽，槽的高度可以是1~4，现在要求锁上至少有两个相邻的槽之间的高度差为3并且至少有3种不同高度的槽，问有几种排列方式
要点：
这题应该是可以通过排列组合简单得出结论的，但是我推不出来，看了一下网上的做法都是用DP记忆化搜索，思路是用dp[i][now][j][m]存储有多少种方案，i表示第i个槽，now表示当前槽的高度，j表示是否达到相邻高度差为3，达到了则为1，m为有m种不同高度。用dfs搜索时引入一个变量s，它用二进制表示已经使用了哪几个高度，如1011，说明1，2，4高度已经使用。
| 15581120 | Seasonal | 1351 | Accepted | 196K | 0MS | C++ | 777B | 2016-06-01 21:46:02 |
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
long long dp[20][5][2][20];
int n;long long dfs(int i, int now, int j, int s, int m)//s作为一个二进制记录哪几个高度已经使用，如1011，说明1，2，4高度已经使用
{if (i >= n){if (j&&m >= 3)return 1;elsereturn 0;}if (dp[i][now][j][m] != -1)return dp[i][now][j][m];long long ans = 0;int temp;for (int k = 1; k <= 4; k++){if (!(s & 1 << (k - 1)))//s中没有k高度temp = m + 1;elsetemp = m;ans += dfs(i + 1, k, (now != 0 && abs(k - now) == 3) || j,s|1<<(k-1), temp);//now不能取一开始的0}dp[i][now][j][m] = ans;return ans;
}int main()
{while (~scanf("%d",&n) && n != -1){memset(dp, -1, sizeof(dp));dfs(0, 0, 0, 0, 0);printf("%d: %lld\n",n,dp[0][0][0][0]);}return 0;
}