MnZn 求调状压dp，WA20pts

Jorisy @ 2023-07-10 18:41:25

by Jorisy @ 2023-07-10 18:41:31

#include<bits/stdc++.h>
#define pc __builtin_popcount
using namespace std;

int n,m,c,a[105],b[105],f[105][105][105];//f[i][now][lst]

void dfs(int dep,int s)
{
    if(dep>m)
    {
        b[++c]=s;
        return;
    }
    dfs(dep+1,s<<1);
    dfs(dep+3,(s|1)<<3);
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int s=0;
        for(int j=1;j<=m;j++)
        {
            char ch;
            cin>>ch;
            s=(s<<1)|(ch=='H');
        }
        a[i]=s;
    }
    dfs(1,0);
    for(int i=1;i<=c;i++)
    {
        if(a[1]&b[i]) continue;
        f[1][i][0]=pc(b[i]);
    }//line 1
    for(int i=1;i<=c;i++)
    {
        if(a[2]&b[i]) continue;
        for(int j=1;j<=c;j++)
        {
            if(b[i]&b[j]||a[1]&b[j]) continue;
            f[2][i][j]=f[1][j][0]+pc(b[i]);
        }
    }//line 2
    for(int i=3;i<=n;i++)//now
    {
        for(int j=1;j<=c;j++)//lst
        {
            if(a[i]&b[j]) continue;
            for(int k=1;k<=c;k++)//lst of lst
            {
                if(b[j]&b[k]||a[i-1]&b[k]) continue;
                for(int l=1;l<=c;l++)
                {
                    if(b[j]&b[l]||b[k]&b[l]||a[i-2]&b[l]) continue;
                    f[i][j][k]=max(f[i][j][k],f[i-1][k][l]+pc(b[j]));
                }
            }
        }
    }//line 3~n
    int ans=0;
    for(int i=0;i<=c;i++)
    {
        for(int j=0;j<=c;j++)
        {
            ans=max(ans,f[n][i][j]);
        }
    }
    cout<<ans;
    return 0;
}

by Jorisy @ 2023-07-10 18:42:07

啊，标题写错了，是 10pts