算法1

非常简单的状态压缩dp，一开始用爆搜+位运算优化最大的情况TLE了

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;

int f[6][50][50];

int s[50], idx;

int n, m;

bool check(int stat)
{
    for(int i = 0; i < m; ++ i)
        if(stat & (1 << i))
            if(i + 3 <= m && (stat & (1 << (i + 1))) && (stat & (1 << (i + 2)))) return false;
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < 1 << m; ++ i) if(check(i)) s[idx ++ ] = i;
    for(int i = 0; i < idx; ++ i)
        for(int j = 0; j < idx; ++ j)
            f[2][i][j] = 1;
    for(int i = 3; i <= n; ++ i)
        for(int j = 0; j < idx; ++ j)  
            for(int k = 0; k < idx; ++ k)
                for(int h = 0; h < idx; ++ h)
                    if(!(s[h] & s[k] & s[j]))
                        f[i][j][k] += f[i - 1][k][h];
    int res = 0;
    for(int i = 0; i < idx; ++ i)
        for(int j = 0; j < idx; ++ j)
            res += f[n][i][j];
    if(n == 1) printf("%d", idx);
    else printf("%d", res);
    return 0;
}