HDU 1438 钥匙计数之一
Problem Description
一把锁匙有N个槽，槽深为1，2，3，4。每锁匙至少有3个不同的深度且至少有1对相连的槽其深度之差为3。求这样的锁匙的总数。
Input
本题无输入
Output
对N>=2且N<=31，输出满足要求的锁匙的总数。
Sample Output
N=2: 0 N=3: 8 N=4: 64 N=5: 360 .. .. .. .. .. .. .. N=31: ...
分析：
递推规律，也找不到，下面有参考大佬的规律递推
状态压缩解法也看了好久才看懂，状态压缩有点巧妙啊
#include<iostream>
#include<cstring>
using namespace std;
const int N=40;
long long dp[N][N][N][2];
///第几个槽，前面槽的状态（包含几个不同的深度），最后一个槽的深度，是否已经符合要求
int num[17];
int main()
{
memset(num,0,sizeof(num));
memset(dp,0,sizeof(dp));
for(int i=0;i<16;i++)
for(int j=0;j<4;j++)
if(i&(1<<j))
num[i]++;///找不同的状态不同深度数。从而找出合法的至少有3个深度不同
for(int i=0;i<4;i++)///初始化1只有1,2,3,4四个状态。
dp[1][1<<i][i][0]=1;
for(int i=2;i<32;i++)///槽数
for(int j=0;j<16;j++)///不同深度状态
for(int k=0;k<4;k++)///前一个槽的最后一个深度
{
for(int l=0;l<4;l++)///当前槽的最后一个的深度
{
int cur=j|(1<<l); ///在j的二进制中第l位变为1（注意从后往前）
dp[i][cur][l][1]+=dp[i-1][j][k][1];
if(k-l==3||k-l==-3)
{
dp[i][cur][l][1]+=dp[i-1][j][k][0];
}
else dp[i][cur][l][0]+=dp[i-1][j][k][0];
}
}
for(int i=2;i<32;i++)
{ long long ans=0;
for(int j=0;j<16;j++)
if(num[j]>=3)///挑出符合条件的超过2个不同深度
for(int k=0;k<4;k++)
ans+=dp[i][j][k][1];
cout<<"N="<<i<<": "<<ans<<"\n";
}
}
又是一题递推题，用递推的思路去解。
说来惭愧，做这题的时候有个地方卡住了，直到看了别人的解题报告才豁然开朗（数学没学好。。）
将lock[n]计做n个凹槽时，符合要求的钥匙总数.
将one[n]计做n个凹槽时，第n个凹槽为1时符合要求的钥匙总数.
将two[n]计做n个凹槽时，第n个凹槽为2时符合要求的钥匙总数.
且1=4,2=3;
对与第n个凹槽，有两种情况。
1.前n-1个凹槽以构成钥匙，那么对于第n个凹槽而言，无论第n个凹槽为1/2/3/4，都有lock[n-1]种情况。
2.前n-1个凹槽未构成钥匙，加了第n个凹槽后才符合钥匙规则，那么分两种情况
A.当第n个凹槽为 2/3时，前面n-1个凹槽必须为1/4构造而成的，出去两种全为1/4的情况，即2^(n-1)-2种情况
B.当第n个凹槽为1/4时，前面n-1个凹槽的构成有多种情况，将这多种情况分析清楚：
假设第n个凹槽为1：
则前面n-1个凹槽的构成情况有如下几种
{
A1.前n-1个凹槽由4种类型组成，但未有相邻两个凹槽高度差为3的。
A2.前n-1个凹槽由4种类型组成，有相邻两个凹槽高度差为3的。
B1.前n-1个凹槽由3种类型组成，但未有相邻两个凹槽高度差为3的。
B2.前n-1个凹槽由3种类型组成，有相邻两个凹槽高度差为3的。
C1.前n-1个凹槽由2种类型组成，但未有相邻两个凹槽高度差为3的。
C2.前n-1个凹槽由2种类型组成，有相邻两个凹槽高度差为3的。
D. 前n-1个凹槽由1种类型组成。
}
由已知条件“前n-1个凹槽未构成钥匙，加了第n个凹槽后才符合钥匙规则”
可以将A2，B2，C2，D的全部情况排除，推得结论n-1个凹槽上必须为4，才符合已知条件。
即：A1+B1+C1=all-(A2+B2+C2+D)=1*4^(n-2)-(one[n-1]+1*2^(n-2)-1+1)
综合以上两种情况：
one[n]=4^(n-2)-(one[n-1]+2^(n-2))+lock[n-1]
two[n]=2^(n-1)-2+lock[n-1]
lock[n]=2*(one[n]+two[n])
参考：https://blog.csdn.net/yuanyunfeng3/article/details/40298903?utm_source=copy
#include<stdio.h>
#include<math.h>
int main()
{
__int64 one[32]={0},two[32]={0},lock[32]={0};
one[3]=2;
lock[2]=0;
lock[3]=8;
printf("N=2: 0\n");
printf("N=3: 8\n");
for(int n=4;n<32;n++)
{
one[n]=(__int64)pow((float)4,n-2)-(__int64)pow((float)2,n-2)-one[n-1]+lock[n-1];
two[n]=(__int64)pow((float)2,n-1)-2+lock[n-1];
lock[n]=2*(one[n]+two[n]);
printf("N=%d: %I64d\n",n,lock[n]);
}
getchar();
return 1;
}