3519炮兵阵地【状态压缩动态规划】

《3519炮兵阵地【状态压缩动态规划】》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、炮兵阵地【状态压缩动态规划】TimeLimit:1000MSMemoryLimit:65536KTotalSubmit:60Accepted:42Description炮兵阵地（cannon.pas/c/cpp）【问题描述】司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“IT表示），也可能是平原（用表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图屮黑色区域所示：pPHPHHPPpHPHPHPPpPPHHHPH

2、HPHPPPPHHPPPPHPHHPPHPHHPHHHPPPPH如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队Z间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。Input文件的第一行包含两个由空格分割开的正整数，分别表示N和M；接下来的N行，每一行含有连续的M个

3、字符CP，或者日，）,中间没有空格。按顺序表示地图中每一行的数据。N<100；M<10oOutput文件仅在第一行包含一个整数K,表示最多能摆放的炮兵部队的数量。SampleInput54PHPPPPHHPPPPPHPPPlIIIPSampleOutput6Hint状态压缩经典案例SourceNOI2001这个是我写的虽答案止确，但时间较长，总时间2mstypean-array[0..11]ofinteger;varn,m,1:integer;a:array[1<•100]ofarr;data,s:arr;b:array[0..100,0..60,0

4、..11]ofinteger;line:array[0..100]ofinteger;f:array[0..100,0..60,0..60]oflongint;f2:array[-4..60]oflongint;q:array[0…60]ofarr;proceduredfs(v:integer);vari,ans:1ongint;beginifdata[v]=lthenbegindfs(v+1);exit;end;ifv>mthenbegininc(l);q[l]:二s;ans:=0;fori:=1tomdoans:=ans+s[i];q[l][0]

5、:=ans;exit;end;s[v]:=0;dfs(v+1);s[v]:=1;ifv<=m-3thendfs(v+3)elsedfs(m+1);s[v]:=0;end;functioncheck(s,x,y,p:longint):boolean;vari:longint;beginfori:二1tomdoif(b[s,x,i]=l)and(b[s-p,y,i]=l)thenexit(false);exit(true);end;functionmax(a,b:longint):longint;beginifa>=bthenexit(a)elseexi

6、t(b);end;procedureinit;vari,j,k,s:integer;maxx:longint;c:char;beginreaclln(n,m);fori:=1tondobeginforj:=ltomdobeginread(c);ifc二'ITthena[i,j]:二1;encl;readln;end;fori:=1tondobegindata:=a[i];1:二0;dfs(l);line[i]:二1;b[i]:二q;end;ifn=lthenbeginfori:=1tomdobeginf2[i]:二f2[i-1];ifa[l,i]二0

7、thenf2[i]:二max(f2[i-3]+l,f2[iT])end;writein(f2[m]);halt;end;fors:-2tondofori:=1tolinc[s]doforj:=1toline[sT]dobeginifnotcheck(s,i,j,1)thenf[s,i,j]:=0;ifs〈二2thenifcheck(s,i,j,1)thenf[s,i,j]:=b[s,i,0]+b[sT,j,0];ifs>2thenifcheck(s,i,j,1)thenbeginmaxx:=0;thenfork:=ltoline[s-2]doifch

8、eck(S,i,k,2)andcheck(s~l,j,k,1)maxx:=max(maxx,f[s~l,j,