状态: Accepted
测评机： Xeost[5]
得分： 100分
提交日期： 2009-4-15 18:57:00
有效耗时： 3440毫秒
测试结果1: 通过本测试点|有效耗时172ms
测试结果2: 通过本测试点|有效耗时47ms
测试结果3: 通过本测试点|有效耗时375ms
测试结果4: 通过本测试点|有效耗时188ms
测试结果5: 通过本测试点|有效耗时375ms
测试结果6: 通过本测试点|有效耗时469ms
测试结果7: 通过本测试点|有效耗时485ms
测试结果8: 通过本测试点|有效耗时172ms
测试结果9: 通过本测试点|有效耗时157ms
测试结果10: 通过本测试点|有效耗时1000ms
上程序 ~ 状态压缩dp经典题
program rqnoj_328；
// 炮兵阵地
// 采用 3 进制状态压缩
// 用一行存两行状态
// 0: 当前行和上一行均未放
// 1: 放在当前行
// 2: 放在上一行
const
maxN = 100；
maxM = 10；
maxState = 59049；
var
N, M: Longint；
i, j, p: Longint；
S: String；
Map: array [-1..maxN, 1..maxM] of Boolean；
F: array [Boolean, 0..maxState - 1] of Longint； // 滚动数组
Ans: Longint；
Flag: Boolean；
procedure dfs(p, s1, s2, b, icr: Longint)；
var
t: Integer；
begin
if p = M then
begin
if F[not Flag, s1] + icr > F[Flag, s2] then
F[Flag, s2] := F[not Flag, s1] + icr
end
else
begin
// 0
// 0
dfs(p + 1, s1 * 3, s2 * 3, b - 1, icr)；
// 1
// 2
if Map[i - 1, p + 1] then
dfs(p + 1, s1 * 3 + 1, s2 * 3 + 2, b - 1, icr)；
// 2
// 0
if Map[i - 2, p + 1] then
dfs(p + 1, s1 * 3 + 2, s2 * 3, b - 1, icr)；
// 0
// 1
if (b <= 0) and Map[i, p + 1] then
dfs(p + 1, s1 * 3, s2 * 3 + 1, 2, icr + 1)
end
end；
begin
readln(N, M)；
p := 1；
for i := 1 to M do
p := p * 3；
dec(p)；
fillchar(Map, sizeof(Map), 0)；
for i := 1 to N do
begin
readln(S)；
for j := 1 to M do
if S[j] = ’P’ then
Map[i, j] := True
end；
fillchar(F, sizeof(F), 0)；
for i := 1 to N do
begin
Flag := odd(i)；
dfs(0, 0, 0, 0, 0)
end；
Ans := 0；
for i := 0 to p do
if F[odd(N), i] > Ans then
Ans := F[odd(N), i]；
writeln(Ans)
end.