炮兵陣地
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 15261 Accepted: 5743
Description
司令部的將軍們打算在N*M的網格地圖上部署他們的炮兵部隊。一個N*M的地圖由N行M列組成，地圖的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下圖。在每一格平原地形上最多可以布置一支炮兵部隊（山地上不能夠部署炮兵部隊）；一支炮兵部隊在地圖上的攻擊范圍如圖中黑色區域所示：
如果在地圖中的灰色所標識的平原上部署一支炮兵部隊，則圖中的黑色的網格表示它能夠攻擊到的區域：沿橫向左右各兩格，沿縱向上下各兩格。圖上其它白色網格均攻擊不到。從圖上可見炮兵的攻擊范圍不受地形的影響。
現在，將軍們規劃如何部署炮兵部隊，在防止誤傷的前提下（保證任何兩支炮兵部隊之間不能互相攻擊，即任何一支炮兵部隊都不在其他支炮兵部隊的攻擊范圍內），在整個地圖區域內最多能夠擺放多少我軍的炮兵部隊。
Input
第一行包含兩個由空格分割開的正整數，分別表示N和M；
接下來的N行，每一行含有連續的M個字符('P'或者'H')，中間沒有空格。按順序表示地圖中每一行的數據。N <= 100；M <= 10。
Output
僅一行，包含一個整數K，表示最多能擺放的炮兵部隊的數量。
Sample Input
5 4
PHPP
PPHH
PPPP
PHPP
PHHPSample Output
6Source
Noi 01
自己寫的一個狀態壓縮，比較激動啊，不過我寫的比別人寫的運行時間要長，希望哪位大神看了可以給個建議
Memory: 1872 KBTime: 422 MSLanguage: CResult: Accepted
<SPAN style="FONT-FAMILY: Times New Roman">#include<stdio.h>
struct recor{
int r[65],num,s[65];
}a[110];//a[i]保存i行的所有滿足水平不重疊要求的狀態
int dp[110][65][65],tem,n,m;
int max(int i,int j)
{
return i>j?i:j;
}
void pb(int i)
{
int j,x,d;
for(j=0;j<1<<m;j++)
{
if(!(j&tem))</SPAN><SPAN style="FONT-FAMILY: 'Times New Roman'">//</SPAN><SPAN style="FONT-FAMILY: 'Times New Roman'">①若是1表示平原0表示高山，這一步便無法找出滿足條件的狀態，新手請手動模擬一下位運算來體會這句話的含義</SPAN><SPAN style="FONT-FAMILY: Times New Roman">
{
if((j&(j<<1))||(j&(j<<2)))//這是排除一行大炮可以攻擊到對方的情況，位運算時一定要注意位運算的優先級，加括號</SPAN><SPAN style="FONT-FAMILY: 'Times New Roman'">
continue;
a[i].r[a[i].num]=j;//保存下一行中滿足題意的狀態
d=j;
x=d%2;
while(d=(d>>1))
{
x+=d%2;
}
a[i].s[a[i].num++]=x;//x表示的是每一個狀態對應的炮數
}
}
}
int main()
{
int i,j,sum,k,p,max;
char c;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<n;i++)
{
a[i].num=0;
tem=0;
getchar();
for(j=0;j<m;j++)
{
c=getchar();
if(c=='P')
tem=(tem<<1);
else tem=(tem<<1)+1;//這個就是把這個圖轉化成二進制tem，0表示平原，1表示高山，我開始不理解為什麼不把平原設成1，那樣1表示可以0表示不可以豈不是更符合我們平常的思維？但是等我那樣寫了我才發現問題，請見標號①
}
pb(i);
}
for(i=1;i<n;i++)
for(j=0;j<a[i].num;j++)
for(p=0;p<a[i-1].num;p++)
dp[i][j][p]=0;//初始化
for(j=0;j<a[0].num;j++)
for(p=0;p<a[0].num;p++)
dp[0][j][p]=a[0].s[j];//同樣也是初始化
for(j=0;j<a[1].num;j++)//因為前兩行有點特殊，所以單獨處理了
for(p=0;p<a[0].num;p++)
if(!(a[1].r[j]&a[0].r[p]))
dp[1][j][p]=dp[0][p][0]+a[1].s[j];
for(i=2;i<n;i++)//每一行
{
for(p=0;p<a[i].num;p++)//每一行的所有狀態
{
max=0;
for(k=0;k<a[i-1].num;k++)//前一行的狀態
{
for(j=0;j<a[i-2].num;j++)//前兩行的狀態
{
if((!(a[i-1].r[k]&a[i-2].r[j]))&&(!(a[i].r[p]&a[i-2].r[j]))&&(!(a[i].r[p]&a[i-1].r[k])))//三行的判斷前後是否有重疊的情況
{
if(dp[i][p][k]<dp[i-1][k][j]+a[i].s[p])
dp[i][p][k]=dp[i-1][k][j]+a[i].s[p];//這就是取最大值了
}
}
}
}
}
max=0;
if(n>1)//好像不用分情況，寫麻煩了，n=1時n-1就是0啊
for(i=0;i<a[n-1].num;i++)
for(j=0;j<a[n-2].num;j++)
{
if(max<dp[n-1][i][j])
max=dp[n-1][i][j];
}
else
for(j=0;j<a[0].num;j++)
{
if(max<dp[0][j][0])
max=dp[0][j][0];
}
printf("%d\n",max);
}
return 0;
}</SPAN>
