可以看做棋子放在某個位置后該種顏色就占領了那一行一列。行列間彼此沒有區別。

　　于是可以設f[i][j][k]表示前k種棋子占領了i行j列的方案數。轉移時枚舉第k種棋子占領幾行幾列。注意行列間是有序的，要乘上一個組合數。這里f[i][j][k]可以是在原棋盤選i行j列占領的方案數，也可以是占領i行j列棋盤的方案數，如果是第二種最后統計答案的時候還要乘上個組合數，轉移略有不同但沒有本質區別。我們還需要計算出k個棋子占領i行j列中的方案數才能轉移。

　　考慮怎么求這個東西。設其為g[i][j][k]。不妨把行列盡量往左往上移，可以發現棋子只能放置在其重合區域，也就是一個i*j的棋盤。使得這里面每行每列都有棋子就可以了。

　　然而還是不太好算?？紤]求存在某一行或某一列沒有棋子的方案數，那么可以枚舉其中有幾行幾列是空的轉移。于是可得g[i][j][k]=C(i*j,k)-Σg[x][y][k]*C(i,x)*C(j,y) (x+y<i+j)。

?

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } #define P 1000000009 #define N 31 #define K 11 int n,m,c,l,a[K],f[K][N][N],g[K][N][N],ans=0; int fac[N*N],inv[N*N],C[N*N][N*N]; void inc(int &x,int y){x+=y;if (x>=P) x-=P;} int main() { #ifndef ONLINE_JUDGEfreopen("bzoj3294.in","r",stdin);freopen("bzoj3294.out","w",stdout);const char LL[]="%I64d"; #elseconst char LL[]="%lld"; #endifn=read(),m=read(),c=read();for (int i=1;i<=c;i++) a[i]=read();C[1][0]=C[1][1]=1;for (int i=2;i<=n*m;i++){C[i][0]=C[i][i]=1;for (int j=1;j<i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;}for (int k=1;k<=c;k++)for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)if (i*j>=a[k]){g[k][i][j]=C[i*j][a[k]];for (int x=1;x<=i;x++)for (int y=1;y<=j;y++)if (x<i||y<j)inc(g[k][i][j],P-1ll*C[i][x]*C[j][y]%P*g[k][x][y]%P);}f[0][0][0]=1;for (int k=1;k<=c;k++)for (int i=k;i<=n;i++)for (int j=k;j<=m;j++)if (i*j>=a[k])for (int x=1;x<=i-k+1;x++)for (int y=1;y<=j-k+1;y++)inc(f[k][i][j],1ll*f[k-1][i-x][j-y]*g[k][x][y]%P*C[n-i+x][x]%P*C[m-j+y][y]%P);for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)inc(ans,f[c][i][j]);cout<<ans;return 0; }

?

轉載于:https://www.cnblogs.com/Gloid/p/9458177.html

總結

以上是生活随笔為你收集整理的BZOJ3294 CQOI2011放棋子（动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。