AzukaVictor @ 2022-03-11 22:00:45
#include<bits/stdc++.h>
using namespace std;
int n,m,st[1<<10],mp[1<<10],dp[101][1<<10][1<<10],num[1<<10],ans;
char c[20];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>c;
for(int j=0;j<m;j++)
{
if(c[j]=='H')
{
mp[i]+=1;
}
mp[i]<<=1;
}
mp[i]>>=1;
}
for(int i=0;i<(1<<m);i++)
{
int sum=0;
for(int j=i;j>0;j>>=1)
{
if((j&1)==1) sum++;
}
num[i]=sum;
if(!(i&(i<<2))&&!(i&(i>>2))&&!(i&(i<<1))&&!(i&(i>>1)))
{
if((mp[1]&i)==0)
dp[1][i][0]=num[i];
st[i]=1;
}
}
for(int i=0;i<(1<<m);i++)
{
for(int j=0;j<(1<<m);j++)
{
if((st[i]&st[j])==1&&(mp[2]&i)==0&&(mp[1]&j)==0&&(i&j)==0)
{
dp[2][i][j]=max(dp[2][i][j],dp[1][j][0]+num[i]);
}
}
}
for(int i=3;i<=n;i++)
{
for(int j=0;j<(1<<m);j++)
{
if(st[j]==1&&(mp[i]&j)==0)
for(int k=0;k<(1<<m);k++)
{
if(st[k]==1&&(j&k)==0&&(k&st[i-1])==0)
for(int f=0;f<(1<<m);f++)
{
if((k&f)==0&&(j&f)==0&&(f&st[i-2])==0&&st[f]==1)
{
dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][f]+num[j]);
}
}
}
}
}
for(int i=0;i<(1<<m);i++)
{
for(int j=0;j<(1<<m);j++)
{
ans=max(ans,dp[n][i][j]);
}
}
cout<<ans<<endl;
return 0;
}
rt,调了半天没出来,也不是优先级问题,求大佬指点
by ZkjTCTC @ 2022-03-25 23:14:57
dp[101][1<<10][1<<10],同志是dp[101][1<<11][1<<11]吧。数据看清楚
by ZkjTCTC @ 2022-03-25 23:18:02
st,num同理。状态也有1111111111啊
by heleans @ 2022-09-17 10:51:32
@ZkjTCTC 1111111111不也在1<<10范围内吗