讨论 / RP爆发....
wish 2010-08-17 20:03:00
点我顶贴 收藏 删除
终于RP爆发。。。。。经过无数次优化之后。。。

状态: 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.

#1 lychees@2009-04-15 19:19:00
回复 删除
sofa...- -
#2 wish@2009-04-15 19:19:00
回复 删除
散分...
#3 lychees@2009-04-15 19:20:00
回复 删除
#24

(..智能ABC打不出 jiong 字...)

#4 Aule@2009-08-01 20:06:00
回复 删除
问lz:杯具论是什么东西
#5 小小小学生@2009-09-25 17:38:00
回复 删除
回复LS: 杯具=悲剧
#6 leapoahead@2010-08-17 20:03:00
回复 删除
= =

1000ms

牛逼

查看更多回复
提交回复