我靠，一下午加一晚上，还是对着别人的代码，终于看懂了，自己的也A了。 自己能力太差了，大家一起继续努力啊。
这是我找到的算是最容易理解的题解了，慢慢看，开始看时是有点苦逼的，加油。
思路：
把底边贴着第 x 行底边放置的芯片 称为第 x 行芯片。
由于芯片长度只有 3， 所以第 x 行芯片的放置只受 x-1行 和 x-2 行放置情况的影响。
同时由于一旦 方格 （x-1, y）被黑色记号或其他芯片 占据，则方格（x-2,y）即便空闲对第 x行芯片的放置也毫无意义。
所以，只需记录的状态只有：
一， a[x] = 0 表示方格（x-1,y）空闲，方格（x-2,y）空闲
二， a[x] = 1 表示方格（x-1,y）空闲，方格（x-2,y）被占据
三， a[x] = 2, 表示方格（x-1,y）被占据
意味着对于 I 层， 其状态 J， 保存着 I，I-1 层 芯片的放置方法，
所以我们通过 dp（I，J）更新 I+1 层时，同样要更新 I+1 的状态信息 K， 其保存着 I+1， I层信息
状态 dp（i,j）表示 前 i 层 状态为 J 的最大芯片数量
情况一， 当前列y 不放，从 y+1 列开始考虑
情况二， 当前两列 ( y, y+1 ) 合法，放 3*2 芯片， 更新 I+1层状态 ， 再去考虑 y+2列
情况三， 当前三列（y,y+1,y+2）合法，放 2*3 芯片， 更新 I+1 层状态，再去考虑 y+3列
这里因为 3^10 接近 60000， 又行数 n = 150, 因为只需要保存两层间关系，所以可以通过滚动数组来 优化空间。
另，处理列的组合问题需要 递归DFS，通过回溯来解决。 另外，对于黑点，我们其实可以合并到 芯片占据的类型中去，
而不需要单独处理，这样就能同过 I层的放置序列 P（p1,p2,...,pm），I+1层的放置序列Q （Q1，Q2，。。，Qm），来决策了。
自己写的太挫了，帖别人的吧。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
const int N = 60000;
int vis[155][11];
int dp[2][60000], A[11], P[11], Q[11];
int n, m, K, mask;
inline int MAX(int a,int b)
{
return a>b?a:b;
}
int GetState( int f[] )
{
int res = 0;
for(int i = 1; i <= m; i++)
res += (f[i]*A[i-1]);//转换为3进制数的十进制
return res;
}
void GetBack( int x, int f[] )
{
for(int i = 1; i <= m; i++)
{
f[i] = x%3; x /= 3;//一共有m列 所以用此数组保存状态。
}
}
void dfs( int i, int x, int num) // 第i行，x列， 数量为num
{
if( x > m ) return;
int cur = (i+1)&1, nxt = i&1, k = GetState(Q) ;
// 当前层可不放任意芯片
dp[nxt][k] = MAX( dp[nxt][k], dp[cur][ GetState(P)]);
//情况（1） 当方格 (i+1,x) 不放置芯片时，那么考虑方格(i+1,x), 且 x < m
//情况（2） 如果 P[x],P[x+1] = 0, 且区域 (i-1,i+1), (x,x+1)均无黑点 且 i >= 2 && x < m
//则 竖立放置芯片 3*2， 左下角坐标为 （i+1,x）
if( (x<=(m-1)) && ( (P[x]==0) && (P[x+1]==0) ) && ( (Q[x]==0)&&(Q[x+1]==0)) )
{
Q[x] = Q[x+1] = 2; //横着放的
int kk = GetState(Q);
dp[nxt][kk] = MAX( dp[nxt][kk], num+1 );//这样就保证一直保存其最大值。
dfs( i, x+2, num+1 );
Q[x] = Q[x+1] = 0;
}
//情况（3） 如果 P[x],P[x+1],P[x+2] <= 1, 且区域 (i,i+1),(x,x+2) 均无黑点 且 i >= 1 && x < m-1
//则 横着放置芯片 2*3, 左下角坐标为 (i+1,x)
if( (x<=(m-2)) && ( (!Q[x])&&(!Q[x+1])&&(!Q[x+2]) ) )
{
Q[x]=Q[x+1]=Q[x+2] = 2; //竖着放的
int kk = GetState(Q);
dp[nxt][kk] = MAX( dp[nxt][kk], num+1 );
dfs( i, x+3, num+1);
Q[x]=Q[x+1]=Q[x+2] = 0;
}
dfs( i, x+1, num );
}
void solve()
{
// 初始化为 -1，标明该 状态不可用
memset( dp, 0xff, sizeof(dp) );
memset( P, 0, sizeof(P));
memset( Q, 0, sizeof(Q));
for(int i = 1; i <= m; i++)
P[i] = vis[1][i]+1; //损坏点看作 已占用。。
// 初始化第一层状态， 抽象把第0层看作皆被占用，合法状态仅一种，且方案数为0
dp[1][ GetState(P) ] = 0;
mask = A[m];
// 0: i,i-1层位置皆为空
// 1：i层为空，i-1层已占用
// 2：i层已占用 此时i-1层的作为就没有了
for(int i = 2; i <= n; i++)
{
int cur = (i+1)&1, nxt= i&1;//位与1可用来求奇偶
// 已知 dp(i,j) 状态j表示 i,i-1层 放置编号
// 初始化下一层nxt，初始时皆为不可用
memset( dp[nxt], 0xff, sizeof(dp[nxt]) );
for(int j = 0; j < mask; j++)
{
if( dp[cur][j] == -1 ) continue; //若当前状态不合法
//I层 放置编号J 解压成 放置序列 P[]
GetBack( j, P );
//获取 I+1层 放置序列 Q[], 且把第I+1层 损坏位置看做已占用，添加到状态中
for(int x = 1; x <= m; x++)
{
if( vis[i][x] ) Q[x] = 2;
else
{ //去除掉 I-1层 的信息，存储I，I+1放置信息
Q[x] = P[x]-1;
if( Q[x] < 0 ) Q[x] = 0;
}
}
// 获取第I+1行 放置状态以及数量
dfs( i, 1, dp[cur][j] ); //行i,列j，目前芯片数量 dp[cur][j]
}
}
int ans = 0;
for(int i = 0; i < mask; i++)
ans = MAX( ans, MAX(dp[0][i],dp[1][i]) );
printf("%d\n", ans );
}
int main()
{
A[0] = 1;
for(int i = 1; i <= 10; i++ ) A[i] = 3*A[i-1];//这数组是将10进制的数转换为3进制数所需要的
int T;
scanf("%d", &T);
while( T-- )
{
scanf("%d%d%d", &n,&m,&K);
int x, y;
memset( vis, 0, sizeof(vis));
for(int i = 0; i < K; i++)
{
scanf("%d%d", &x,&y);
vis[x][y] = 1;
}
solve();
}
return 0;
}