問題

還是宇宙時間公元 5.5 5.5億年， maxingc maxingc maxingc maxingc聯盟用微子來攻擊 yunyunyun聯盟。憤怒的 yunyun 聯盟決定反戈一擊，他們 準備使用加農炮來反擊。
yunyun 聯盟的將軍們打算在 N*M 的網格地圖上部署他們炮兵隊。一個 的網格地圖上部署他們炮兵隊。一個 N*M 的地圖由 N行 M列組成，地 列組成，地 圖的每一格可能是山地（用 圖的每一格可能是山地（用 "H" "H" 表示），也可能是平原（用 表示），也可能是平原（用 表示），也可能是平原（用 表示），也可能是平原（用 "P" "P"表示），如下圖。在每一格平原 表示），如下圖。在每一格平原 表示），如下圖。在每一格平原 表示），如下圖。在每一格平原 地形上最多可 以布置一支炮兵部隊（山地上不能夠署）；在圖的攻擊范圍如中黑色區域所 以布置一支炮兵部隊（山地上不能夠署）；在圖的攻擊范圍如中黑色區域所 以布置一支炮兵部隊（山地上不能夠署）；在圖的攻擊范圍如中黑色區域所 以布置一支炮兵部隊（山地上不能夠署）；在圖的攻擊范圍如中黑色區域所 示：

如果在地圖中的灰色所標識平原上部署一支炮兵隊，則黑網格表示它能夠攻擊到區域：沿橫向左右各兩格，縱上下。圖其它白色網均攻擊不到從可見炮兵的范圍受地形的影響。 現在，將軍們規劃如何部署炮兵隊防止誤傷的 前提下（保證任何兩支炮兵部隊之間不能互相攻擊， 即任何一支炮 兵部隊都不在其他的攻擊范圍內），整個地圖區域最多能夠擺放少我軍即任何一支炮 兵部隊都不在其他的攻擊范圍內），整個地圖區域最多能夠擺放少我軍即任何一支炮 兵部隊都不在其他的攻擊范圍內），整個地圖區域最多能夠擺放少我軍兵部隊。
第一行包含兩個由空格分割開的正整數，別表示 N和 M； 接下來的 N行，每一含有連續的 行，每一含有連續的 M個字符 ('P'('P' 或者 'H') 'H') ，中間沒有空格。 按順序表示地圖每一行的數據，中間沒有空格。 按順序表示地圖每一行的數據，中間沒有空格。 按順序表示地圖每一行的數據，中間沒有空格。 按順序表示地圖每一行的數據N <= 100= 100= 100 ；M <= 10 。
僅一行，包含個整數 K，表示最多能擺放的炮兵部隊數量。
分析

這個題的n<=100 ,m<=10。如果盲目搜索，肯定會超時。

由于m<=10,所以每一行的狀態可以用二進制表示，放置炮兵記為1，不放置記為0。

每一行的狀態只和前兩行的狀態有關系，所以有方程：

F[i,k1,k2]=Max{f[i-1,k2,k3]+num[k1]},其中i為行數，k1表示第i行的狀態，k2表示第i-1行的狀態，k3表示第i-2行的狀態，num[k1]為k1狀態下可放置炮兵的個數。

i,k1，k2，k3必須滿足一定的關系（炮兵之間不能相互攻擊，且炮兵不能放在山地上）。

1

第i行放第k1種狀態，第i-1行放第k2種狀態，會不會出現矛盾

對于狀態a[k1]和a[k2],如果他們是可行的，討論他們每個對應的位置

a[k1]如果某位置是1,a[k2]這位上必須是0

a[k1]如果某位置是0,a[k2]這位上可以是1，也可以是0

所以可以歸納出 a[k1] and a[k2]=0，這要判斷矛盾可以使速度大大提高

2.

對于每一行，第i種狀態能不能放上去，即要求不能在‘H’的地方放士兵

我們可以先把每行原來的初始狀態也表示出來，但是這里有個小技巧，把‘H’的地方記錄下來

這行如果某位置是1，那么在a[k1]中這個位置上必須為0（1代表這里是山地）

這行如果某位置是0，那么在a[k1]中這個位置上可以為1，可以為0（0代表這里是平原）

所以可以歸納出 now[i] and a[k1]=0（now數組表示地形的狀態）。

3.

我們可以提前枚舉每種狀態，把本身一行中可以相互攻擊的狀態刪去，對于每一行進行操作時，需要將其轉化成字符串，否則對一個二進制串很難操作。

此時f數組下表表示的是此狀態在狀態數組a中的位置。

View Code program liukeke;
var
now:array[0..101] of longint;
a,b:array[0..102] of longint;
f:array[0..100,0..102,0..102] of longint;
n,m,i,k1,k2,k3,ans,j,tt,sum:longint;
s:string;
flag:boolean;

function max(a,b:longint):longint;
begin
if a>b then exit(a);
exit(b);
end;

procedure init;
var
i,j:longint;
ch:char;
begin
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
begin
read(ch);
if ch='H' then
now[i]:=now[i] + (1<<(m-j));
end;
readln;
end;
end;

function change(x:longint):string;
begin
change:='';
while x>0 do
begin
change:=chr(x mod 2+48)+change;
x:=x div 2;
end;
end;

begin
assign(input,'connon.in');
reset(input);
assign(output,'connon.out');
rewrite(output);
init;
for i:=0 to (1<<m)-1 do
begin
tt:=0;
flag:=false;
s:=change(i);
while length(s)<m do s:='0'+s;
for j:=1 to m do
if s[j]='1' then
begin
if s[j+1]='1' then begin flag:=true; break; end;
if s[j+2]='1' then begin flag:=true; break; end;
inc(tt);
end;
if not flag then
begin
inc(sum);
a[sum]:=i;
b[sum]:=tt;
end;
end;
for i:=1 to sum do
f[1,i,1]:=b[i];
for i:=2 to n do
for k1:=1 to sum do
for k2:=1 to sum do
if (a[k1] and a[k2]=0)and(a[k1] and now[i]=0)and(a[k2] and now[i-1]=0)then
for k3:=1 to sum do
if (a[k1] and a[k3]=0)and(a[k2] and a[k3]=0)and(a[k3] and now[i-2]=0)then
f[i,k1,k2]:=max(f[i,k1,k2],f[i-1,k2,k3]+b[k1]);
for i:=1 to sum do
for j:=1 to sum do
if (a[i]and a[j]=0)and(a[i] and now[n]=0)and(a[j] and now[n-1]=0)then
ans:=max(ans,f[n,i,j]);
writeln(ans);
close(input);
close(output);
end.

轉載于:https://www.cnblogs.com/liukeke/archive/2011/06/12/2079058.html

總結

以上是生活随笔為你收集整理的【动态规划】炮兵阵地的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。