开O2还是T了一半的点，不知道是哪里写假了还是状压转移有问题，求大佬看看

bobzbh @ 2023-02-12 21:17:24

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define N 110
#define M 11
using namespace std;
int dp[N][(1<<M)-1][(1<<M)-1];
//表示行，状态，上一行状态 
int n,m,st,pic[N]; 
int cul[(1<<M)-1];
//预处理每个数的二进制下1的个数 
void init(int num)
{
    for(int i=1; i<=num; ++i)
    {
        int tot=0,state=i;
        while(state!=0)
        {
            if(state&1==1)
            {
                tot++;
            }
            state>>=1;
        }
        cul[i]=tot;
    }
}
int main()
{
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    st=(1<<m)-1;//状态总数 
    init(st);
    for(int i=1; i<=n; ++i)
    {
        char row[M];
        int state=0;
        cin>>row;
        for(int j=0; j<m; ++j)
        {
            //将地形状态压缩成一个数字H是1，P是0 
            state<<=1;
            if(row[j]=='H')
            {
                state+=1;
            }
        }
        pic[i]=state;
    }
    int ans=0;
    for(int i=1; i<=n; ++i)//第和i行 
    {
        for(int j=0; j<=st; ++j)//当前行状态 
        {
            if((j&pic[i])==0&&(j&(j<<2))==0&&(j&(j<<1))==0)
            {
                for(int k=0; k<=st; ++k)//上一行状态 
                {
                    for(int l=0; l<=st; ++l)//上上行状态 
                    {
                        if((k&j)==0&&(l&j)==0)
                        {
                            dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][l]+cul[j]);
                        }
                    }
                    if(i==n)
                    {
                        ans=max(ans,dp[i][j][k]);
                    }
                }
            }
        }
    }
    cout<<ans;
    return 0;
}
/*
1 1
P
*/

by stupid_collie @ 2023-03-08 22:54:12

改好了 把第44行的加法改成了或运算（不过影响不大） 在枚举k和j的时候额外判断了一下k和j本身是否合法，就能拍出很多不合法的情况了 完整代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define N 110
#define M 11
using namespace std;
int dp[N][(1<<M)-1][(1<<M)-1];
int n,m,st,pic[N];
int cul[(1<<M)-1];
void init(int num)
{
    for(int i=1; i<=num; ++i)
    {
        int tot=0,state=i;
        while(state!=0)
        {
            if(state&1==1)
            {
                tot++;
            }
            state>>=1;
        }
        cul[i]=tot;
    }
}
int main()
{
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    st=(1<<m)-1;
    init(st);
    for(int i=1; i<=n; ++i)
    {
      string row;
        int state=0;
        cin>>row;
        for(int j=0; j<m; ++j)
        {
            if(row[j]=='H')
            {
              state|=(1<<j);
            }
        }
        pic[i]=state;
    }
    int ans=0;

    for(int i=1; i<=n; ++i)
    {
        for(int j=0; j<=st; ++j)
        {
            if((j&pic[i])==0&&(j&(j<<2))==0&&(j&(j<<1))==0)
            {
                for(int k=0; k<=st; ++k)
                {
                  if((k&(k<<2))||(k&(k<<1)))continue;
                    for(int l=0; l<=st; ++l)
                    {
                      if((l&(l<<2))||(l&(l<<1)))continue;
                        if((k&j)==0&&(l&j)==0)
                        {
                          dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][l]+cul[j]);
                        }
                    }
                    if(i==n)
                    {
                        ans=max(ans,dp[i][j][k]);
                    }
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

（因为用的emacs编辑，所以缩进有点奇怪qwq）