思路

都说是三进制，但是参考了网上的思路，可以把三行看作一个状态，用二进制来表示：
第一行 state1 第二行 state2<<m 第三行 state3<<(2*m)

不要用数组的下标表示状态，即b[state]
而要用数组的结果表示状态，即b[cnt] = state

#include<bits/stdc++.h> 
using namespace std;
int t, n, m, k;
int cnt, cnt2;
int a[155], b[3050], f[155][3050], c[3050], g[3050], r[3050], p[305][305]; //第i行 前两行状态为g[j]
void dfs(int i, int state, int geshu)//第i列
{
    if( i == m ) 
    {
        b[ ++cnt ] = state; //三行的状态是一个state
        c[ cnt ] = geshu;//这三行放了几个
        return;
    }
    dfs(i+1, state, geshu);
    if( i+3 <= m)
    dfs(i+3, state|(7<<i)|(7<<(i+m)), geshu+1);//放入横的长方体 i到i+2列是1 下一行的i到i+2列也是1
    if( i+2 <= m)
    dfs(i+2, state|(3<<i)|(3<<(i+m)|(3<<(i+2*m))), geshu+1);//放入竖的长方体 i到i+1列是1 下两行的i到i+1列也是1
}


int main()
{
    cin >> t;
    while( t -- )
    {
        int ans = 0;
        cin >> n >> m >> k;
        cnt = 0;
        cnt2 = 0;
        memset(a, 0, sizeof a);
        memset(f, 0, sizeof f);
        cnt = 0; cnt2 = 0;
        dfs(0, 0, 0);
        for(int i = 1; i <= cnt; i++)
            for(int j = 1; j <= cnt; j++){
                if( ( (b[i]>>m) & b[j] ) == 0)//如果这一行的“第二行”与下一行的“第一行”不冲突
                {
                    r[ ++ cnt2 ] = j; p[i][j] = cnt2;//r表示两行的放置方案中下面一行的状态
                    g[ cnt2 ] = (b[i] >> m) | b[j];//两行放置方案
                }
            }
        for(int i=1; i <= k; i ++ )
        {
            int x, y;
            cin >> x >> y;
            a[x]|=1<<(y-1);//第x行第y列有障碍
        }
        a[n+1] = (1<<m) - 1;//最后一行全是障碍

        for(int i = 1; i <= n; i ++ )//第i行
        {
            a[i] |= (a[i+1]<<m) | (a[i+2]<<(2*m)); //第i与i+1与i+2行障碍都放在第i行内

            for(int j = 1; j <= cnt2; j++)//前两行的放置方案数
                for(int kk = 1; kk <= cnt; kk++)//这一行尝试所有的放置方案数
                    if( ( ( (g[j]>>m) | a[i]) & b[kk])==0 )//与前面和障碍不会冲突
                    {
                        f[i][ p[r[j]][kk] ] = max(f[i][ p[r[j]][kk] ], f[i-1][j] + c[kk]);
                        ans = max(ans, f[i][ p[r[j]][kk] ]);
                    }
        }
        cout << ans << endl;
    }
    return 0;
}