对于复杂度的一些疑问

这是一段AC代码

#include <bits/stdc++.h>
using namespace std;
int dx[111],f[2][1024][1024],n,m,s,siz[1111],ans,ls=0;
//int pre[111][1111][2];
bool check(int x)
{
    return x&(x<<1)||x&(x<<2)||x&(x>>1)||x&(x>>2);
}
int sz(int x)
{
    int sum=0;
    while(x)
    {
        sum+=x&1;
        x>>=1;
    }
    return sum;
}
int main()
{
    cin>>n>>m;
    s=(1<<m);
    for(int j=0;j<s;j++) 
    {
        siz[j]=sz(j);
    //  printf("%d ",siz[j]);
        if(check(j)) continue;
        f[1][j][0]=siz[j];
    }
//  for(int i=1;i<=n;i++) for(int j=0;j<s;j++) printf("%d %d %d\n",i,j,f[i][j]);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char c=getchar();
            while(c!='P'&&c!='H') c=getchar();
            dx[i]<<=1;
            if(c=='H') dx[i]+=1;
        }
    }

    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<s;j++)
        {
            if(j&dx[i]) continue;
            if(check(j)) continue;
            for(int k=0;k<s;k++)
            {
                if(j&k||k&dx[i-1]) continue;
                if(check(k)) continue;
                ls=0;
                for(int k1=0;k1<s;k1++)
                {
                    if(k1&k||k1&dx[i-2]||k1&j) continue;
                    if(check(k1)) continue;
                    ls=max(ls,f[(i-1)%2][k][k1]);
                }
                f[i%2][j][k]=ls+siz[j];
            //  printf("%d %d %d %d\n",i,j,k,f[i][j][k]);
            }
        }
    }
    for(int j=0;j<s;j++) for(int k=0;k<s;k++) if(!(j&dx[n])&&!(k&j)&&!(k&dx[n-1])) ans=max(ans,f[n%2][j][k]);
    cout<<ans;
    return 0;
}

理论上复杂度已经到了n2^(3m)，基本上凉的很彻底

但实际上由于远远没有跑满，所以总时间1.68s，最大的也就500ms

所以我想问一下各位大佬，有无对这个状压复杂度较为良好具体的分析

十分感谢！！！