题意：

锁上有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

Accepted

196K

0MS

777B

2016-06-01 21:46:02

#include
    
     #include
     
      #include
      
       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;		else			return 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;		else			temp = 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;}