UVA 861 组合数学递推

题目链接 https://vjudge.net/problem/UVA-861

题意：一个国际象棋棋盘，‘象’会攻击自己所在位置对角线上的棋子。问n*n的棋盘摆放k个互相不攻击的 '象' 有多少种方式。

解析：我们知道国际象棋的棋盘是黑交替所以容易知道放在白格上的棋子和放在黑格上的棋子是不会互相攻击的。所以把白格和黑的分别拿出来讨论

相当于从白格里面拿i个从黑格里面拿k-i个的方案数(0<=i<=k) 我们就开始处理从白格里面拿i个的方案数，我们把矩阵旋转45度看

W
B B
WWW

B B B B
WWWWW
B B B B
WWW
B B
W

然后调整一下

WWW

WWWWW

变成了这样 dp[ i ] [ j ] 表示前 i 行放置 j 个棋子的方案数，假设第 i 行没有棋子，方案数就是dp[ i-1 ] [ j ], 假设第 i 行有棋子方案数就是dp[ i-1 ][ j-1 ] * ( a[ i ] - (i-1) ) ( a[ i ]表示当前

行的列数，减去前面被占用的行，就是当前行的选择数 ). 黑色格子一样.

代码

 1 #include <bits/stdc++.h>
 2 #define pb push_back
 3 #define mp make_pair
 4 #define fi first
 5 #define se second
 6 #define all(a) (a).begin(), (a).end()
 7 #define fillchar(a, x) memset(a, x, sizeof(a))
 8 #define huan printf("
");
 9 #define debug(a,b) cout<<a<<" "<<b<<" ";
10 using namespace std;
11 typedef long long ll;
12 const int maxn=100,maxm=100,inf=0x3f3f3f3f;
13 const ll mod=1000000007;
14 ll a[maxn],b[maxn];
15 ll dpa[maxn][maxn],dpb[maxn][maxn];
16 int main()
17 {
18     int n,k;
19     while(cin>>n>>k)
20     {
21         if(n==0)
22             return 0;
23         fillchar(a,0);
24         fillchar(b,0);
25         fillchar(dpa,0);
26         fillchar(dpb,0);
27         int cnt1=1,cnt2=1;
28         for(int i=1;i<n;i++)
29             if(i%2==1)
30             {
31                 a[cnt1++]=i;
32                 a[cnt1++]=i;
33             }
34         for(int i=1;i<n;i++)
35             if(i%2==0)
36             {
37                 b[cnt2++]=i;
38                 b[cnt2++]=i;
39             }
40         if(n%2==0)
41             b[cnt2++]=n;
42         else
43             a[cnt1++]=n;
44         dpa[0][0]=1;
45         for(int i=1;i<cnt1;i++)
46         {
47             dpa[i][0]=1;
48             for(int j=1;j<=k;j++)
49             {
50                 dpa[i][j]=dpa[i-1][j]+dpa[i-1][j-1]*(a[i]-j+1);
51             }
52         }
53         dpb[0][0]=1;
54         for(int i=1;i<cnt2;i++)
55         {
56             dpb[i][0]=1;
57             for(int j=1;j<=k;j++)
58             {
59                 dpb[i][j]=dpb[i-1][j]+dpb[i-1][j-1]*(b[i]-j+1);
60             }
61         }
62         ll sum=0;
63         for(int i=0;i<=k;i++)
64         {
65             sum+=dpa[cnt1-1][i]*dpb[cnt2-1][k-i];
66         }
67         cout<<sum<<endl;
68     }
69 }

UVA 861 组合数学 递推

UVA 861 组合数学递推