WorldBest丶牛顿 @ 2018-10-26 20:26:40
先说问题:为什么这么写布星qwq
#include<bits/stdc++.h>
using namespace std;
int max(int a,int b){return a>b?a:b;}
int n,m,ans;
char s[11];
int num[1027];
int a[101][101];
int f[101][101][101];
//f[所在行][所在行的状态][上一行的状态]
void add_num(int x)
{
if(num[x]) return;
int a=x;
while(x)
{
x&=x-1;
num[a]++;
}
}//算出这种状态有多少部队
int main()
{
std::ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1,t;i<=n;++i)
{
cin>>s;t=0;
for(int j=0;j<m;++j)
if(s[j]=='P') t=t<<1;
else t=t<<1|1;
for(int j=0;j<(1<<m);++j)
{
if((j&(j<<1))||(j&(j<<2))||(j&t)) continue;
a[i][++a[i][0]]=j;//储存各种状态
add_num(j);
}
}//a[i][j]存放可以放部队的位置
a[0][0]=1;
for(int i=1;i<=a[1][0];++i)
f[1][i][1]=num[a[1][i]];
for(int i=2;i<=n;++i)
for(int j=1;j<=a[i][0];++j)
for(int k=1;k<=a[i-1][0];++k)
for(int l=1;l<=a[i-2][0];++l)//注意这里有个l,debug的时候看清楚
if(!(a[i][j]&a[i-1][k]&a[i-2][l]))
f[i][j][k]=max(f[i][j][k],f[i-1][k][l]+num[a[i][j]]);
for(int i=1;i<=a[n][0];++i)
for(int j=1;j<=a[n-1][0];++j)
ans=max(ans,f[n][i][j]);
cout<<ans;
return 0;
}
by WorldBest丶牛顿 @ 2018-10-26 21:08:06
by WorldBest丶牛顿 @ 2018-10-26 21:30:53
我想通了: