中文题。。
思路：这题可把我恶心坏了，我刚开始的思路其实是正确的。。。
首先我想开个dp[i][s1][s2]保存到 i行 为止当前行状态为s1，上一行状态为s2 的最大个数，然后我先把满足行内条件的
状态存起来，空间用滚动数组优化，但是我在写转移方程的时候发现复杂度太大。。。。 其实复杂度是够的，因为一行里面
满足行内条件的最多有60个合法状态，哈希一下就好啦，都不用滚动数组。。。
然后我又开脑洞去搞三进制的状态压缩，写到最后发现复杂度又不对，才发现原来的方法是正确的。。。。
#include<cstdio>
#include<vector>
#define fi first
#define se second
#define mk make_pair
#define pii pair<int,int>
#define read(x) scanf("%d",&x)
#define sread(x) scanf("%s",x)
#define dread(x) scanf("%lf",&x)
#define lread(x) scanf("%lld",&x)
using namespace std; typedef long long ll;
const int inf=0x3f3f3f3f;
const int INF=0x3f3f3f3f3f3f3f3f;
const int N=;
const int M=;
const int mod=1e8; int n,m,dp[][][],f[N];
char s[];
vector<int> v,num;
bool check(int x)
{
int cnt=,cur=x;
while(x)
{
int now=x%;
if(cnt< && now)
return false;
if(now) cnt=;
else cnt++;
x/=;
}
return true;
}
int cal(int x)
{
int ans=;
while(x)
x-=x&-x,ans++;
return ans;
}
int main()
{
read(n); read(m);
for(int i=;i<n;i++)
{
scanf("%s",s);
for(int j=;j<m;j++)
f[i]*=,f[i]+=s[j]=='P'? :;
}
int up=<<m;
for(int i=;i<up;i++)
{
if(check(i))
{
v.push_back(i);
num.push_back(cal(i));
}
}
int sz=v.size();
for(int i=;i<sz;i++)
{
int s1=v[i];
if((s1|f[])!=f[])
continue;
for(int j=;j<sz;j++)
{
int s2=v[j];
if((s2|f[])!=f[] || (s1&s2))
continue;
dp[][i][j]=num[i]+num[j];
}
}
for(int i=;i<n;i++)
{
for(int j=;j<sz;j++)
{
for(int k=;k<sz;k++)
{
for(int u=;u<sz;u++)
{
int s1=v[j],s2=v[k],s3=v[u];
if((s1&s2) || (s1&s3) || (s1|f[i])!=f[i])
continue;
dp[i][k][j]=max(dp[i][k][j],dp[i-][u][k]+num[j]);
}
}
}
}
int ans=;
if(n!=)
{
for(int i=;i<sz;i++)
for(int j=;j<sz;j++)
ans=max(ans,dp[n-][i][j]);
}
else
{
for(int i=;i<sz;i++)
if((v[i]|f[])==f[])
ans=max(ans,num[i]);
}
printf("%d\n",ans);
}
/*
*/