TLE了，哪位大佬帮我优化一下

Belarus @ 2019-08-24 15:50:04

#include<bits/stdc++.h>
using namespace std;
const int maxn=102,maxm=11;
int n,m,a[maxn],f[3][(1<<maxm)-1][(1<<maxm)-1],ans;
inline int count(int x){
    int cnt=0;
    for(int i=m-1;i>=0;i--) if((x>>i)&1) cnt++;
    return cnt;
}
inline bool valid(int row,int x){
    if(x&(x>>1)) return false;
    if(x&(x>>2)) return false;
    if(x&(x<<1)) return false;
    if(x&(x<<2)) return false;
    else for(int i=m-1;i>=0;i--){
        if(((x>>i)&1)&&(!((a[row]>>i)&1)))
         return false;
    }
    return true;
}
int main(){
    ios::sync_with_stdio(0);
    memset(f,-0x3f,sizeof(f));
    cin>>n>>m;
    char c;
    for(int i=1;i<=n;i++)
     for(int j=0;j<m;j++){
        cin>>c;
        while(c!='P' && c!='H') 
         cin>>c;
        if(c=='P') a[i]|=(1<<j);
     }
    f[0][0][0]=0;
    for(int j=0;j<(1<<m);j++)
     if(valid(1,j))
      f[1][j][0]=count(j);
    for(int i=2;i<=n;i++)
     for(int j=0;j<(1<<m);j++)
      if(valid(i,j))
       for(int k=0;k<(1<<m);k++)
        if((k&j)==0)
         if(valid(i-1,k))
          for(int l=0;l<(1<<m);l++)
           if((j&l)==0) 
            f[i%3][j][k]=max(f[i%3][j][k],f[(i-1)%3][k][l]+count(j));
    for(int j=0;j<(1<<m);j++)
     if(valid(n,j))
      for(int k=0;k<(1<<m);k++)
       if((k&j)==0)
        if(valid(n-1,k))
         ans=max(ans,f[n%3][j][k]);
    cout<<ans;
    return 0;
}

by Belarus @ 2019-08-24 16:20:03

AC了，谢谢大家 用STL预处理的

#include<bits/stdc++.h>
using namespace std;
const int maxn=102,maxm=11;
int n,m,a[maxn],f[3][(1<<maxm)-1][(1<<maxm)-1],ans;
set<int> s;
set<int>::iterator it;
set<int>::iterator it2;
set<int>::iterator it3;
inline int count(int x){
    int num=0;
    while(x) x-=(x&-x),num++;
    return num;
}
inline bool valid(int row,int x){
    for(int i=m-1;i>=0;i--){
        if(((x>>i)&1)&&(!((a[row]>>i)&1)))
         return false;
    }
    return true;
}
int main(){
    freopen("pbzd.in","r",stdin);
    ios::sync_with_stdio(0);
    memset(f,-0x3f,sizeof(f));
    cin>>n>>m;
    char c;
    for(int i=1;i<=n;i++)
     for(int j=0;j<m;j++){
        cin>>c;
        while(c!='P' && c!='H') 
         cin>>c;
        if(c=='P') a[i]|=(1<<j);
     }
    for(int i=0;i<(1<<m);i++){
        if(i&(i>>1)) continue;
        if(i&(i>>2)) continue;
        if(i&(i<<1)) continue;
        if(i&(i<<2)) continue;
        s.insert(i);
    }
    f[0][0][0]=0;
    for(it=s.begin();it!=s.end();it++)
     if(valid(1,*it))
      f[1][*it][0]=count(*it);
    for(int i=2;i<=n;i++)
     for(it=s.begin();it!=s.end();it++)
      if(valid(i,*it))
       for(it2=s.begin();it2!=s.end();it2++)
        if(((*it2)&(*it))==0)
         if(valid(i-1,*it2))
          for(it3=s.begin();it3!=s.end();it3++)
           if(((*it)&(*it3))==0) 
            f[i%3][*it][*it2]=max(f[i%3][*it][*it2],f[(i-1)%3][*it2][*it3]+count(*it));
    for(it=s.begin();it!=s.end();it++)
     if(valid(n,*it))
      for(it2=s.begin();it2!=s.end();it2++)
       if(((*it2)&(*it))==0)
        if(valid(n-1,*it2))
         ans=max(ans,f[n%3][*it][*it2]);
    cout<<ans;
    return 0;
}