http://acm.hdu.edu.cn/showproblem.php?pid=5079
给你一个 n⋅n(n≤8) 的棋盘,上面有一些格子必须是黑色,其它可以染黑或者染白,对于一个棋盘,定义它的优美度为它上面最大的连续白色子正方形的边长,对于每个 0≤i≤n ,问有多少种染色方案使得棋盘的优美度为 i ?
2014 Asia AnShan Regional Contest,by WJMZBMR.
比较显然的是这个题可以拆成
真是蛋疼到极点。。。不过经过上面的思考，问题就能简化为求出最大白色正方形边长小于
这里需要解释一下每一行的状态,它实际上就是一个最小表示法的数字，这个数字中的第
i
位表示的是该行从第i个格子到第i+sz-1个格子中每个格子往上走的连续白格子个数的最小值。
注意我上面加的粗体，是为了方便断句，避免由断句引起歧义。
那么我们就能从第
很显然DP方程为
dp[i][newsta]=∑dp[i−1][sta]
然后再求
dp[i][j]
的补集，即最大xxxx大于等于i的方案数，暂且叫
dp′[i][j]吧，dp′[i][j]=2|可以染色的格子集合|−dp[i][j]
然后求
ans′[]
数组，
ans′[sz]=∑dp[n][S]，此时ans′[sz]=优美度大于等于sz的方案数
，然后
求出ans[]数组，ans[sz]=优美度为sz的方案数，很显然ans[sz]=ans′[sz]−ans′[sz+1]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#define MAXN 12
#define MAXM 120000
#define MOD 1000000007
using namespace std;
int n,m,k; //n*n大小的棋盘，m=2^(可以填颜色的格子个数),k=最大白色正方形边长不超过sz的情况下
char s[MAXN];
int a[MAXN]; //a[i]=第i行不能填颜色的格子状态
int ans[MAXN]; //ans[sz]=白色正方形边长最小为sz的方案数
int powsz[MAXN];
int dp[MAXN][MAXM]; //dp[i][j]=在第i行，状态为j的方案数
int flag[MAXN]; //flag[i]=1表示当前行中
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(a,0,sizeof(a));
m=1;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
//cout<<"m: "<<m<<endl;
scanf("%s",s);
for(int j=0;j<n;j++)
{
if(s[j]=='o')
m=m*2%MOD;
else
a[i]|=1<<j;
}
}
//cout<<"ddm: "<<m<<endl;
ans[0]=1; //最小白色正方形边长为0，即全黑棋盘的方案数为1
ans[1]=(m-1+MOD)%MOD; //最小白色正方形边长为1的方案数为2^(可以填颜色的格子个数)-1(相当于一个集合的所有子集个数)
for(int sz=2;sz<=n;sz++) //求最小正方形为sz的方案数
{
powsz[0]=1; //powsz[i]=sz^i
k=n+1-sz;
for(int i=1;i<=k;i++)
powsz[i]=powsz[i-1]*sz;
dp[0][0]=1;
for(int st=1;st<powsz[k];st++) //清零
dp[0][st]=0;
for(int i=1;i<=n;i++) //DP到第i行
{
for(int st=0;st<powsz[k];st++) //!!!!!清零
dp[i][st]=0;
for(int cur=0;cur<(1<<n);cur++) //暴力枚举把集合cur中的格子都染成黑色
{
if(cur&a[i]) continue; //有不能染色的格子在集合cur中，不合法
for(int j=0;j<k;j++)
flag[j]=0;
for(int bit=0;bit<n;bit++) //枚举该行的第bit列的格子
{
if(cur&(1<<bit)) continue; //这个格子是不能被染色的
for(int j=0;j<k;j++)
if(bit>=j&&bit<j+sz)
flag[j]=1;
}
for(int st=0;st<powsz[k];st++) //枚举第i行的状态st
{
if(!dp[i-1][st]) continue; //不合法的状态
int newst=0; //newst=由第i-1行推出的第i行的状态
for(int j=0;j<k;j++)
{
int t=st/powsz[j]%sz; //t是sz进制数st中的第j位数字
if(flag[j]) t=0;
else if(t!=sz-1) t++;
else
{
newst=-1;
break;
}
newst+=t*powsz[j];
}
if(newst==-1) continue; //由f[i-1][st]推出的f[i][st]为非法状态
dp[i][newst]=(dp[i][newst]+dp[i-1][st])%MOD;
}
}
}
ans[sz]=0;
for(int st=0;st<powsz[k];st++)
ans[sz]=(ans[sz]+dp[n][st])%MOD;
ans[sz]=(m-ans[sz]+MOD)%MOD; //求ans[sz]的补集后，此时ans[sz]=最小白色正方形边长大于等于sz的方案数
ans[sz-1]=(ans[sz-1]-ans[sz]+MOD)%MOD;
}
for(int sz=0;sz<=n;sz++)
printf("%d\n",ans[sz]);
}
return 0;
}