b_vj_Number of Locks（状态压缩+记忆化搜索）

弹簧锁有n个槽(n<=17)，每个槽的高度可以是{1,2,3,4}中的中的任何一个。在锁的槽中，至少有一对相邻的槽，其高度差等于3，并且锁的槽至少有3个不同的高度值。 查找所符合上述条件的锁的数量。

思路：要记录的东西有这么几个：

• 当前槽的位置i
• 前一个相邻槽的高度j
• 到目前位置槽高度的种类k
• 目前槽的选择情况s

当前n个槽都选完高度以后，过程中出现过高度差≥3的情况我们才返回1，所以还要用变量tag记录这种情况是否出现过

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
typedef long long ll;
const int N=18;
int n;
ll f[N][5][5][2]; //f[i][j][k][0/1]表示第i个槽位的高度为j，有k种不同高度，没有/有相邻的槽位高度差为3
ll dfs(int i, int j, int k, int l, int s) { //第i层，lastH=j，k种高度，是否l达成相高度差=3，所有槽位的高度状态s
    if (i>=n) return l && k>=3 ? 1 : 0;
    if (f[i][j][k][l]) return f[i][j][k][l];
    ll ans=0, nk;
    for (int h=1; h<=4; h++) {
        if ((s&(1<<(h-1)))==0) nk=k+1;
        else nk=k;
        ans+=dfs(i+1,h,nk,(j!=0 && abs(j-h)==3)||l,s|1<<(h-1));
    }
    return f[i][j][k][l]=ans;
}
int main() {
    while (scanf("%d", &n), n!=-1) {
        memset(f,0,sizeof f);
        printf("%d: %lld
", n, dfs(0,0,0,0,0));
    }
    return 0;
}

bug：当n为ll时，WA了...