Little Bishops（棋盘禁区排列）

2018-08-17

[Little Bishops](https://vjudge.net/problem/UVA-861)

题意

在国际棋盘中，象的走法是斜对角线，也就是说两个象不能容于一条斜对角线。国际象棋有黑白两色格子相交组成。给你n*n的棋盘和k个象，问你在满足任意两个象互不相斥的情况下，摆放的最大种数？

思路

利用棋盘禁区排列这一思想。

首先我们可以看到，在棋盘中，黑色的格子和白色的格子上的象绝对不会相斥，所以我们可以根据$R_k(C)=R_i(C_1)*R_{k-i}(C-C_1)$得，Ans就是在黑色棋盘上放i个象的种类乘以在白色棋盘上放k-i个象的种数。

为了将黑白棋盘分开，比如要建立一个方便的白色棋盘，斜着看显然不舒服，那么我们就：

先把黑色格子删去，然后我们斜+45度看这个棋盘，把一斜看做一行，一斜中的格子数就是一行的格子数，同样的，斜-45度就是列中的格子数。又因为每行互换位置并不影响最终结果，因此我们可以把原本对称的棋盘行，进行格数从小到大排序，得到最终的棋盘。

注意，由于黑白棋盘不一样，对于一个n*n的棋盘来说，斜+45度看一共有2n-1个斜行，因此我们这里让白色棋盘占n行，黑色占n-1行，然后用另外的一个数组来存每行中有多少格子（列），基本的构造棋盘就完成了。

对于构造出来的棋盘（如白色），分析一下：

设mp[i][j]表示前i行放j个棋子的种数。那么有
$$
mp[i][j]=mp[i-1][j]+mp[i-1][j-1]·(c[i]-(j-1))
$$
相当于=前i-1行放了j个棋子，这一行不放的种数，加上前i-1行放了j-1个棋子乘以这一行只能在（格子数-已经被j-1个象占了的格子数量）个格子。

对两个棋盘都进行这样的操作即可。

最后的答案就是$\sum_{i=0}^{k}R_i(C_{white})·R_{k-i}(C_{black})$

看！代码

#include <bits/stdc++.h>
using namespace std;
int mp1[10][70],mp2[10][70];
int c1[10],c2[10];
int main()
{
    int n,k;
    while(~scanf("%d%d",&n,&k))
    {
        if(n==0&&k==0) break;
        if(n==1)
        {
            if(k==1||k==0) printf("1\n");
            else printf("0\n");
            continue;
        }
        memset(mp1,0,sizeof(mp1));
        memset(mp2,0,sizeof(mp2));

        for(int i=1;i<=n;i++) //白色棋盘
        {
            if(i&1) c1[i]=i;
            else c1[i]=c1[i-1]; //printf("i:%d\n",c1[i]);
        }
        for(int i=1;i<=n-1;i++) //黑色棋盘
        {
            if(i&1) c2[i]=i+1;
            else c2[i]=i;

        }
        for(int i=0;i<=n;i++)
            mp1[i][0]=mp2[i][0]=1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=k;j++)
            mp1[i][j]=mp1[i-1][j]+mp1[i-1][j-1]*(c1[i]-j+1);
        
        for(int i=1;i<=n-1;i++)
            for(int j=1;j<=k;j++)
            mp2[i][j]=mp2[i-1][j]+mp2[i-1][j-1]*(c2[i]-j+1);
        long long ans=0;
        for(int i=0;i<=k;i++)
            ans+=1ll*mp1[n][i]*mp2[n-1][k-i];

        printf("%lld\n",ans);
    }
    return 0;
}