有一个\(n\times m\)的网格,第i行第j列有一个字符\(c[i][j]\)=P or H,分别表示此处为平原和山,只有平原才能放炮,炮的攻击范围为向上下左右2格,如图黑色为攻击范围,灰色为放炮的位置,现在要求求出网格图中最多可以放炮的个数,并保证炮炮之间不能互相攻击,\(n\leq 100,m\leq 10\)。
m的范围已经告诉你可以进制压缩,但是状态却有三种,于是延伸两种办法
法一:二进制压缩
二进制当然是最快的,于是可以设\(f[i][j][k]\)表示处理到第i行且第i行的状态为j,第i-1行状态为k的能放的最多的炮的数量,显然设j中有1的位置为有炮的位置,而注意到这样做会超时,非法状态太多,于是可以预处理每一行合法的状态,以此作为转移依据,设\(a[i][j]\)为第i行第j个合法状态的二进制数,自然\(f[i][j][k]\)的j对应的是\(a[i][j]\),k对应的是\(a[i-1][k]\),并预处理\(B[i]\)表示i的二进制位下有多少个1,于是我们有
\[f[i][j][k]=\max_{l=0}^{2^m-1}(f[i-1][k][l])+B[a[i][j]](!(a[i][j]\&a[i-1][k])\&\&!(a[i][j]\&a[i-2][l])\&\&!(a[i-1][k]\&a[i-2][l]))\]
边界:\(f[1][i][0]=bit[a[1][i]],i=1,2,..,|a[1]|\)
答案:\(\max_{i=j=0}^{2^m-1}(f[n][i][j])\)
参考代码:
#include <iostream>
#include <cstdio>
#define il inline
#define ri register
using namespace std;
char M[15];
int a[101][501],at[101],
dp[101][501][501],bit[2048];
il int max(int,int);
int main(){
int n,m,li;
scanf("%d%d",&n,&m),li=(1<<m)-1;
for(int i(0);i<=li;++i)
for(int j(m-1);j>=0;--j)
if(i>>j&1)++bit[i];
for(int i(1);i<=n;++i){
scanf("%s",M);
for(int j(0),k,l;j<=li;++j){
for(l=100,k=m-1;k>=0;--k)
if(j>>k&1){if(M[k]=='H'||l-k<3)break;l=k;}
if(k<0)a[i][++at[i]]=j;
}
}++at[0];
for(int i(1);i<=at[1];++i)dp[1][i][1]=bit[a[1][i]];
for(int i(2);i<=n;++i)
for(int j(1);j<=at[i];++j)
for(int k(1);k<=at[i-1];++k){
if(a[i][j]&a[i-1][k])continue;
for(int l(1);l<=at[i-2];++l){
if(a[i-2][l]&a[i][j]||a[i-2][l]&a[i-1][k])continue;
dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][l]);
}dp[i][j][k]+=bit[a[i][j]];
}
int ans(0);
for(int i(1);i<=at[n];++i)
for(int j(1);j<=at[n-1];++j)
ans=max(ans,dp[n][i][j]);
printf("%d\n",ans);
return 0;
}
il int max(int a,int b){
return a>b?a:b;
}
法二:三进制压缩
因为存在三种状态,所以自然的想法是三进制压缩,2表示有炮,1表示炮的上下左右的一格攻击范围,因为多进制的合法判断的速度远远不如二进制,于是我们需要dfs实现转移,而且要尽可能地多多特判非法状态。
#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
using namespace std;
char ar[101][11];
int h,s,t,m,bit[11],
dp[101][59050],b[11];
void dfs(int,int);
il int max(int,int);
il void div3(int,int[]);
int main(){
int n;bit[0]=1;
scanf("%d%d",&n,&m);
for(int i(1);i<=m;++i)bit[i]=bit[i-1]*3;
for(int i(1);i<=n;++i)scanf("%s",ar[i]);
memset(dp,-127,sizeof(dp)),dp[0][0]=0;
for(h=0;h<n;++h)
for(s=0;s<bit[m];++s)
if(dp[h][s]>=0)
div3(s,b),dfs(0,-100);
int ans(0);
for(int i(0);i<bit[m];++i)ans=max(ans,dp[n][i]);
printf("%d",ans);
return 0;
}
il int max(int a,int b){
return a>b?a:b;
}
il void div3(int x,int a[]){
for(int i(m-1);i>=0;--i)
a[i]=x/bit[i]%3;
}
void dfs(int p,int li){
if(p==m){
int tot(0);
for(int i(m-1);i>=0;--i)if(t/bit[i]%3==2)++tot;
dp[h+1][t]=max(dp[h+1][t],dp[h][s]+tot);
return;
}
if(b[p]==0){
dfs(p+1,li);
if(p-li>2&&ar[h+1][p]=='P')
t+=bit[p]<<1,dfs(p+1,p),t-=bit[p]<<1;
}
else if(b[p]==1)dfs(p+1,li);
else t+=bit[p],dfs(p+1,li),t-=bit[p];
}
原文:https://www.cnblogs.com/a1b3c7d9/p/10940384.html