状压 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;
}