天南月 @ 2019-06-25 21:16:20
#include<iostream>
#include<math.h>
#include<cstring>
#include<string>
#include<map>
using namespace std;
int n,m;
int F[105],gs[70];
int dp[105][70][70];
int s[70];
map<char,int>p;
int max(int a,int b){
return a>b?a:b;
}
int main(){
char ch;
p['P']=1;
p['H']=0;
cin>>n>>m;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cin>>ch;
F[i]=(F[i]<<1)+p[ch];
}
}
int len=0,ma=0,maxn=(1<<m);
for(int i=0;i<maxn;++i)
if((!(i&(i<<2)))&&(!(i&(i<<1)))){
s[++len]=i;
int l=i;
while(l){
gs[len]+=(l&1);
l>>=1;
}
}
int ans=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=len;++j)
for(int z=1;z<=len;++z)
for(int k=1;k<=len;++k)
if(((s[k]&F[i])==s[k])&&(!(s[k]&s[z]))&&(!(s[k]&s[j]))&&(!(s[j]&s[z])))
dp[i][j][z]=max(dp[i][j][z],dp[i-1][z][k]+gs[j]);
}
for(int i=1;i<=len;++i)
for(int j=1;j<=len;++j)
ans=max(ans,dp[n][i][j]);
cout<<ans;
return 0;
}
by 天南月 @ 2019-06-25 21:31:09
此帖完结
by LJB00131 @ 2019-06-25 21:44:52
说起来map有log的复杂度,不要乱用
by LJB00131 @ 2019-06-25 21:46:39
@wy99804496
by disangan233 @ 2019-06-25 21:49:39
@LJB00131 Orz 您会map
by LJB00131 @ 2019-06-25 21:52:16
@disangan233
没怎么用过。。。
by LJB00131 @ 2019-06-25 21:53:08
我弱啊
by jiangby @ 2019-06-25 22:11:20
@disangan233 orz
by 天南月 @ 2019-06-26 09:09:12
@LJB00131 只有俩元素没有问题吧?