190040257a @ 2020-08-18 20:06:59
这题我的思路是设
对于$i,s$枚举第$i-2$行的炮兵状态$s1$,第$i-1$行炮兵状态$s2$，第$i$行炮兵状态$s$，如果$s,s2,s1$不冲突
有$f[i][s]=max(f[i-2][s1]+count(s)+count(s2))
```cpp
#include<iostream>
#include<queue>
#include<cstdio>
#include<cmath>
using namespace std;
int f[110][1030];
int a[110][12];
int count(int s)
{
int sum=0;
while(s)
{
sum++;
s=s&(s-1);
}
return sum;
}
int sc[10002];
int cun[190][2000];
int main()
{
int N,M;
cin>>N>>M;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{
char ch;
cin>>ch;
if(ch=='P')
{
a[i][j]=1;
}
}
}
for(int i=1;i<=N;i++)
{
int s=0;
for(int j=1;j<=M;j++)
{
s=(s<<1);
if(a[i][j]==1) s++;
}
sc[i]=s;//用sc来保存每行可放阵地的位置
}
for(int i=1;i<=N;i++)
{
int s=sc[i];
for(int j=0;j<=(1<<M)-1;j++)
{
if(j&(j<<1))continue;
if(j&(j<<2))continue;
if(j&(j>>1))continue;
if(j&(j>>2))continue;
if((j&s)==j)
{
cun[i][0]++;
cun[i][cun[i][0]]=j;
}//提前处理每行的可行状态
}
}
for(int j=1;j<=cun[1][0];j++)
{
int s=cun[1][j];
f[1][s]=count(s);
}
for(int j=1;j<=cun[2][0];j++)
{
int s1=cun[2][j];
for(int l=1;l<=cun[1][0];l++)
{
int s2=cun[1][l];
if(s1&s2) continue;
f[2][s1]=max(f[2][s1],f[1][s2]+count(s1));
}
}
for(int i=3;i<=N;i++)
{
for(int j=1;j<=cun[i-2][0];j++)
{
int s1=cun[i-2][j];
for(int k=1;k<=cun[i-1][0];k++)
{
int s2=cun[i-1][k];
if(s1&s2)continue;
for(int l=1;l<=cun[i][0];l++)
{
int s3=cun[i][l];
if((s1&s3)||(s2&s3)) continue;
f[i][s3]=max(f[i][s3],f[i-2][s1]+count(s2)+count(s3));//前i行总阵地数=前i-2行总数+i-1行阵地数+第i行阵地数
}
}
}
}
int maxn=0;
for(int i=1;i<=cun[N][0];i++)
{
maxn=max(f[N][cun[N][i]],maxn);
}
cout<<maxn;
return 0;
}
```
我自己感觉思路没什么问题，不知道是不是测试数据太水，时间全都是500ms以内，但是WA了8个点