状态压缩DP（三进制压缩）。
由于第i行的放置受到第i-1和i-2行放置情况的影响。我们用0表示方格(i-1,j)和(i-2,j)未放置炮兵；1表示方格(i-1,j)未放炮兵，方格(i-2,j)已被放上炮兵；2表示方格(i-1,j)被放上了炮兵。那么第i-1行和i-2行的放置情况可以用m位的三进制表示。如果放置情况为0,对应的第i行才可以放炮兵，为1和2都不能放。
f[i][j]表示前i行放置好后,并且放置情况为j时炮兵的最大数量。详细见代码：
#include<iostream>
using namespace std;
int n,m;
int map[105][15];
int f[2][60000];
int b[15],s[15];
void dfs(int i,int j,int cur,int sta,int num)
{
if(cur>m)
{
if(f[i&1][sta]<f[(i-1)&1][j]+num)
f[i&1][sta]=f[(i-1)&1][j]+num;
return;
}
int t,d;
if(s[cur]>0) t=s[cur]-1;
else t=0;
d=sta+t*b[cur-1];
dfs(i,j,cur+1,d,num);
if(map[i][cur]=='P'&&s[cur]==0)
{
d=sta+2*b[cur-1];
if(cur+1<=m)
{
if(s[cur+1]>0) t=s[cur+1]-1;
else t=0;
d+=t*b[cur];
}
if(cur+2<=m)
{
if(s[cur+2]>0) t=s[cur+2]-1;
else t=0;
d+=t*b[cur+1];
}
dfs(i,j,cur+3,d,num+1);
}
}
int main()
{
int i,j,k;
b[0]=1;
for(i=1;i<=10;i++) b[i]=b[i-1]*3;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=n;i++)
{
getchar();
for(j=1;j<=m;j++)
scanf("%c",&map[i][j]);
}
memset(f,-1,sizeof(f));
f[0][0]=0;
for(i=1;i<=n;i++)
{
for(j=0;j<b[m];j++) f[i&1][j]=-1;
for(j=0;j<b[m];j++)
{
if(f[(i-1)&1][j]!=-1)
{
s[0]=1;
int v=j;
for(k=1;k<=m;k++)
{
s[k]=v%3;
v/=3;
}
dfs(i,j,1,0,0);
}
}
}
int ans=-1;
for(i=0;i<b[m];i++)
if(ans<f[n&1][i]) ans=f[n&1][i];
printf("%d\n",ans);
}
return 0;
}
posted on 2010-08-15 22:08
wuxu 阅读(116)
评论(0) 编辑 收藏 引用 所属分类:
动态规划