炮兵阵地
Agemt
·
·
题解
一道经典的状压DP
主要思路：用f数组表示状态，首先f数组必有一维表示当前行，还有一维表示当前行的状态，由于炮兵可以轰炸到前两行，所以还需要一维表示上一行的状态，不妨设f[i][j][k]表示第k行的状态为j，第k-1行的状态i时能放的最大炮兵数
不过为什么第k-2行不用记录呢？其实将第k-2行的状态记录进f数组中未尝不可，但不仅会远远超出空间范围(O(2^102^102^10*100))，而且在后面的状态转移方程中我们可以发现不需要考虑第k-2行，在进行第k-1的转移时已经考虑过了
动态转移方程应该很好推 f[i][j][k] = max{ f[l][i][k-1] | l,i,j∈{0,1,...,(1<<m)-1}, k∈{x|x∈N*,x≠1}，check(i,j,l)}
上式表明了状态转移的规律，以及式子成立的条件，观察上述式子，可以再次证明不需要考虑第k-2行，因为在进行第k-1的转移时已经考虑过了，只需要枚举判断第k-2行的状态是否不与第k-1行和第k行冲突
那么check(i,j,k)要满足什么条件呢？不难发现，除了每一行自身状态不能冲突外，每一行之间也不能冲突，这一点在代码中有体现
不过按照这样的思路，还不算优秀，时间复杂度和空间复杂度都较高
针对空间复杂度，由于状态的转移只涉及前一行，我们可以采取滚动数组的方法，将第三维变为[2],楼上的大佬们有详细的讲解
针对时间复杂度，由于在一行中可能有许多不能放置炮兵的点，不妨预处理出，每一行满足地形条件的状态，代码中有较详细说明
代码
#include<bits/stdc++.h>
using namespace std;
struct state{
int st[1100];
int num=0;
}b[110];
int f[1100][1100][2];
int a[110][20];
int s[110],sum[1100];
int n,m,ans,t=1;
int main(){
scanf("%d%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
char c;cin>>c;
s[i]=s[i]*2+(c=='P');//记录每一行状态
}
for(int i=0;i<(1<<m);i++)
for(int j=0;j<m;j++)
if(i&(1<<j)) sum[i]++;//记录每一种状态有几个炮兵
for(int i=1;i<=n;i++)//枚举每一行
for(int j=0;j<(1<<m);j++)//枚举当前行的状态
if((j|s[i])==s[i]&&!(j&(j<<1))&&!(j&(j<<2)))//不冲突
b[i].st[++b[i].num]=j;//记录当前行可行状态
for(int i=1;i<=b[1].num;i++) f[0][b[1].st[i]][0]=sum[b[1].st[i]];//初始化第一行
for(int i=1;i<=b[2].num;i++)//初始化第二行
for(int j=1;j<=b[1].num;j++){
int k=b[2].st[i],l=b[1].st[j];
if(k&l) continue;
f[l][k][1]=max(f[l][k][1],f[0][l][0]+sum[k]);
}
for(int i=3;i<=n;i++){//枚举行
t^=1;//滚动数组
for(int j=1;j<=b[i].num;j++)//第i行状态
for(int k=1;k<=b[i-1].num;k++)//第i-1行状态
if(!(b[i].st[j]&b[i-1].st[k]))//第i行与第i-1行不冲突
for(int l=1;l<=b[i-2].num;l++)//第i-2行状态
if(!(b[i].st[j]&b[i-2].st[l])&&!(b[i-1].st[k]&b[i-2].st[l]))//第i行与第i-2行以及第i-1行与第i-2行不冲突
f[b[i-1].st[k]][b[i].st[j]][t]=max(f[b[i-2].st[l]][b[i-1].st[k]][t^1]+sum[b[i].st[j]],f[b[i-1].st[k]][b[i].st[j]][t]);//更新答案
}
for(int i=1;i<=b[n].num;i++)
for(int j=1;j<=b[n-1].num;j++)
ans=max(ans,f[b[n-1].st[j]][b[n].st[i]][t]);//更新最优解
cout<<ans<<endl;
return 0;
}