題目大意
要求你在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
;
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
