蒟蒻求助10分

状压 dp

#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
int a[101][11];
int stj[101][201];
int sta[101][201];
int n,m;
int cur[101];
int dp[101][201][1001];

void dfs(int ttt,int x,int cnt,int t)
{
//  printf("%d %d %d %d\n",ttt,x,cnt,t);
    if(t >= m)
    {
        stj[ttt][++cur[ttt]] = x;
        sta[ttt][cur[ttt]] = cnt;
        return;
    }
    if(a[ttt][t+1] == 1)
    {
        dfs(ttt,x+(1 << t),cnt+1,t+3);
    }
    dfs(ttt,x,cnt,t+1);
}

bool check(int i,int j,int k,int r)
{
    if(stj[i][j]&stj[i-2][r])
    {
        return false;
    }
    if(stj[i-1][k]&stj[i-2][r])
    {
        return false;
    }
    return true;
}

int main()
{
    memset(dp,0,sizeof(dp));
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            char t;
            cin >> t;
            if(t == 'P')
            {
                a[i][j] = 1;
            }
            else
            {
                a[i][j] = 0;
            }
        }
    }
    for(int i = 1;i <= n;i++)
    {
        dfs(i,0,0,0);
//      printf("%d\n",cur[i]);
    }
    for(int i = 1;i <= cur[1];i++)
    {
        dp[1][i][sta[1][i]] = 1;
    }
    for(int j = 1;j <= cur[2];j++)
    {
        for(int k = 1;k <= cur[1];k++)
        {
            if(stj[2][j]&stj[1][k])
            {
                continue;
            }
            for(int l = sta[2][j];l <= n*m;l++)
            {
                dp[2][j][l] += dp[1][k][l-sta[2][j]];
            }
        }
    }
    for(int i = 3;i <= n;i++)
    {
        for(int j = 1;j <= cur[i];j++)
        {
            for(int k = 1;k <= cur[i-1];k++)
            {
                if(stj[i][j]&stj[i-1][k])
                {
                    continue;
                }
                for(int r = 1;r <= cur[i-2];r++)
                {
                    if(check(i,j,k,r) == false)
                    {
                        continue;
                    }
                    for(int l = sta[i][j];l <= n*m;l++)
                    {
                        if(l-sta[i][j] >= sta[i-1][k])
                        {
                            dp[i][j][l] += dp[i-2][r][l-sta[i][j]-sta[i-1][k]];
                        }
                        dp[i][j][l] += dp[i-1][k][l-sta[i][j]];
                    }
                }
            }
        }
    }
    for(int j = n*m;j >= 0;j--)
    {
        for(int i = 1;i <= cur[n];i++)
        {
            if(dp[n][i][j] > 0)
            {
                printf("%d\n",i);
                printf("%d\n",j);
                return 0;
            }
        }
    }
    return 0;
}