【GDOI2017模拟8.15】Game

Description

给出一个n*m的网格图。 你可以决定每个格子是0还是1. 给出n+m个限制，每个限制限制每行或每列有且只有多少块连续的1. 一块连续的1指的就是一块连续的1（呵呵 两块连续的1就像这样：1…101…1 求方案数。 n<=5,m<=20

Solution

n最大为5，这让我想起了什么不好的东西(雾 似乎某位大爷说过，n这么小那么就状压DP呀！ 但是如何处理每行的限制？ 既然只有5行，那么就开5维来记录喽~=_= 设F[i,j,k1,k2,k3,k4,k5]表示，当前做到第i列，这一列的状态为j，每一行当前的块数分别是k1,k2,k3,k4,k5的方案数。 转移显然。 然后，因为对列的限制是一定的，所以我们可以预处理出每列能有的状态。 对于当前我们做到i这列，我们最多产生了i/2+i%2个块。 同理，因为我们要达到m个块，我们最少要有m-(m-i)/2-(m-i)%2块。 然后就起飞了~~233

Code

#include<cstdio> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int mo=1000000007; int n,m,ans,tot,mi[6],f[21][33][11][11][11][11][11],a[6],b[21],g[11][33]; bool check(int x,int y) { int la=0,count=0; while (x) { if (!la&&x%2) count++; la=x%2;x/=2; } if (count==y) return 1;else return 0; } int calc(int x) {return x/2+x%2;} int main() { scanf("%d%d",&n,&m);mi[0]=1;fo(i,1,n) mi[i]=mi[i-1]*2; fo(i,1,n) scanf("%d",&a[i]); fo(i,1,m) scanf("%d",&b[i]); fo(i,0,10) fo(j,0,mi[n]-1) if (check(j,i)) g[i][++g[i][0]]=j; f[0][0][0][0][0][0][0]=1; fo(i,0,m-1) fo(j,0,mi[n]-1) fo(_1,max(a[1]-calc(m-i),0),min(calc(i),a[1])) fo(_2,max(a[2]-calc(m-i),0),min(calc(i),a[2])) fo(_3,max(a[3]-calc(m-i),0),min(calc(i),a[3])) fo(_4,max(a[4]-calc(m-i),0),min(calc(i),a[4])) fo(_5,max(a[5]-calc(m-i),0),min(calc(i),a[5])) if (f[i][j][_1][_2][_3][_4][_5]) fo(k,1,g[b[i+1]][0]) { int x=g[b[i+1]][k];bool pd=0;int c[6]; c[1]=_1;c[2]=_2;c[3]=_3;c[4]=_4;c[5]=_5; fo(l,1,n) if (!(j&mi[l-1])&&x&mi[l-1]) {c[l]++;if (c[l]>a[l]) {pd=1;break;}} if (pd) continue; f[i+1][x][c[1]][c[2]][c[3]][c[4]][c[5]]+=f[i][j][_1][_2][_3][_4][_5]; if (f[i+1][x][c[1]][c[2]][c[3]][c[4]][c[5]]>mo) f[i+1][x][c[1]][c[2]][c[3]][c[4]][c[5]]-=mo; } fo(i,1,g[b[m]][0]) { ans+=f[m][g[b[m]][i]][a[1]][a[2]][a[3]][a[4]][a[5]]; if (ans>mo) ans-=mo; } printf("%d",ans); }

哎啊，好像太长装不下，大家自己将就着看吧~