div2的F题，只想到了一个复杂度略高的dp，T了几次，后来加了剪枝减掉一些无用的状态终于过了。。
题意：
一个n*m的矩阵 (n<=5,m<=20)，对格子进行黑白染色，已经给出了每行每列黑色联通块的个数，要求输出一组答案，满足有解。
思路：
首先发现n只有5，考虑按列处理，每列总共有2^5=32种状态；又发现对于给出的联通块个数，最坏情况是当联通块个数等于1或者2的时候有15种情况
比直接二进制处理快了一倍。所以我们可以预先处理出联通块个数为0~3时对于的二进制状态；
找到了列的基本状态，现在来考虑转移：
首先在转移时应该满足每行的黑色联通块个数，所以每行当前的联通块个数是需要保存的，由于m<=20所以每行最多有0~10这11种情况，考虑到5行就总共有11^5种状态
所以总共的状态数即为 20*15*11^5=48315300 由于cf的机器很强大这个状态数基本算是可以接受了
转移时处理如下：对于每一行如果上一列为0且当前列为1，则联通块数目+1，其他情况联通块数目不变。
这样我们就可以解决整个dp的过程了，由于题目要求输出染色方案，我们就需要记录每一个状态的前驱，最后通过前驱获得答案
但是直接交上去还是会T的，这里有两个剪枝可以使用
1.在转移过程中如果当前行的联通块个数已经大于题目给的个数，直接把这个状态减掉
2.在转移过程中如果当前行的联通块个数在剩下的列里怎么取(最好情况为一黑一白这样染)都不可能达到题目给的个数，把这个状态减掉
最后终于ac了！
代码：
#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
#include<vector>
using namespace std;
#define MAXN 10000
bool dp[][][];
int pret[];
int x[];
int y[];
int p[];
int ans[];
int v[][];
int nn[];
int n,m;
int fun(int s)
{
int res=;
int pre=;
for(int i=; i<n; i++)
{
if((s&(<<i))&&pre==)
{
res++;
}
pre=(bool)(s&(<<i));
}
return res;
}
inline int get(int s,int i)
{
return (s%p[i+])/p[i];
}
int fuck(int s,int pre,int now,int pos)
{
int res=;
for(int i=; i<n; i++)
{
int tmp=(get(s,i)+((!(pre&(<<i)))&&(now&(<<i))));
if(tmp>x[i])
return -;
if(tmp+(m-pos)/<x[i])
return -;
res+=tmp*p[i];
}
return res;
}
inline int make(int i,int j,int s)
{
return s+j*+i**;
} inline int getj(int t)
{
return (t%(*))/;
} char s[][];
int main()
{
cin>>n>>m;
p[]=;
for(int i=; i<=; i++)
{
p[i]=p[i-]*;
}
for(int i=; i<(<<n); i++)
{
int tmp=fun(i);
v[tmp][nn[tmp]++]=i;
}
for(int i=; i<n; i++)
{
cin>>x[i];
}
for(int i=; i<m; i++)
{
cin>>y[i];
}
for(int i=; i<nn[y[]]; i++)
{
dp[][i][fuck(,,v[y[]][i],)]=;
}
int now,pre,st;
for(int i=; i<m; i++)
{
for(int j=; j<nn[y[i-]]; j++)
{
for(int s=; s<; s++)
{
if(dp[i-][j][s])
{
for(int k=; k<nn[y[i]]; k++)
{
st=fuck(s,v[y[i-]][j],v[y[i]][k],i);
if(st<)
continue;
dp[i][k][st]=;
pret[make(i,k,st)]=make(i-,j,s);
}
}
}
}
}
now=;
for(int i=;i<n;i++)
{
now+=x[i]*p[i];
}
int j=-;
for(int i=;i<nn[y[m-]];i++)
{
if(dp[m-][i][now])
{
j=i;
break;
}
} now=make(m-,j,now);
for(int i=m-;i>=;i--)
{
ans[i]=v[y[i]][getj(now)];
now=pret[now];
}
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
s[i][j]=((ans[j])&(<<i))?'*':'.';
}
}
for(int i=;i<n;i++)
{
puts(s[i]);
}
return ;
}