题目大意
要求你在N*M大小的主板上嵌入2*3大小的芯片，不能够在损坏的格子放置，问最多能够嵌入多少块芯片？
题解
妈蛋，这道题折腾了好久，黑书上的讲解看了好几遍才稍微有点眉目(智商捉急)，接着看了网上大牛的解题报告和实现代码才弄明白怎么用三进制来进行状态压缩,关键就是理解能够横着放置和竖着放置的条件。由于竖着放置会受到前面两行的影响，这样我们就可以用三进制来表示前面两行的状态了，然后根据前面两行的状态我们也可以得到当前行与前一行的初始状态，之后再根据两个的状态进行放置砖块~~~~具体怎么样的看黑书吧
代码：
#include <iostream>
#include
<cstdio>
#include
<cstring>
#include
<algorithm>
using
namespace
std;
#define
MAXN 15
int
dp[
2
][
60000
],pre[MAXN],now[MAXN];
int
mp[MAXN*
10
+
5
][MAXN];
int
s[MAXN],n,m;
int
To_ten(
int
*
a)
{
int
ret=
0
;
for
(
int
i=
1
; i<=m; i++
)
ret
+=a[i]*
s[i];
return
ret;
}
void
To_three(
int
*a,
int
x)
{
for
(
int
i=
1
; i<=m; i++
)
{
a[i]
=x%
3
;
x
/=
3
;
}
}
void
dfs(
int
sum,
int
x,
int
y,
int
status)
{
dp[x][status]
=
max(dp[x][status],sum);
if
(y>=m)
return
;
if
(!pre[y]&&!pre[y+
1
]&&!now[y]&&!now[y+
1
])
{
now[y]
=
2
,now[y+
1
]=
2
;
int
st=
To_ten(now);
dfs(sum
+
1
,x,y+
2
,st);
now[y]
=
0
,now[y+
1
]=
0
;
}
if
((y+
2
<=m)&&!now[y]&&!now[y+
1
]&&!now[y+
2
])
{
now[y]
=
2
,now[y+
1
]=
2
,now[y+
2
]=
2
;
int
st=
To_ten(now);
dfs(sum
+
1
,x,y+
3
,st);
now[y]
=
0
,now[y+
1
]=
0
,now[y+
2
]=
0
;
}
dfs(sum,x,y
+
1
,status);
}
int
main()
{
int
T;
s[
0
]=
0
,s[
1
]=
1
;
for
(
int
i=
2
; i<=
12
; i++
)
s[i]
=s[i-
1
]*
3
;
scanf(
"
%d
"
,&
T);
while
(T--
)
{
int
k;
scanf(
"
%d%d%d
"
,&n,&m,&
k);
memset(dp,
-
1
,
sizeof
(dp));
memset(mp,
0
,
sizeof
(mp));
while
(k--
)
{
int
x,y;
scanf(
"
%d%d
"
,&x,&
y);
mp[x][y]
=
1
;
}
for
(
int
i=
1
; i<=m; i++
)
pre[i]
=mp[
1
][i]+
1
;
int
temp=
To_ten(pre);
dp[
0
][temp]=
0
;
for
(
int
i=
2
; i<=n; i++
)
{
memset(dp[(i
+
1
)&
1
],-
1
,
sizeof
(dp[(i+
1
)&
1
]));
for
(
int
j=
0
; j<s[m+
1
]; j++
)
if
(dp[i&
1
][j]!=-
1
)
{
To_three(pre,j);
for
(
int
p=
1
; p<=m; p++
)
if
(mp[i][p])
now[p]
=
2
;
else
now[p]
=max(
0
,pre[p]-
1
);
temp
=
To_ten(now);
dfs(dp[i
&
1
][j],(i+
1
)&
1
,
1
,temp);
}
}
int
ans=
0
;
for
(
int
i=
0
; i<s[m+
1
]; i++
)
ans
=max(ans,dp[(n+
1
)&
1
][i]);
printf(
"
%d\n
"
,ans);
}
return
0
;
}
