UVA 10237 - Bishops

题目链接
题意：问一个n * n棋盘能放k个主教（攻击斜线）的方案数。

思路：递推，首先考虑一个问题，在一个n n棋盘上，放k个车的方案数。
那么设dp[i][j]为i行用了j个车的方案数，由于每行只能放一个车，那么考虑i行放不放车，如果放车，那么能放的位置有n (j 1)个位置，为dp[i 1][j 1] (n (j 1))。
如果不放那么情况为dp[i 1][j]。
所以递推式为dp[i][j]=dp[i][j 1]+dp[i 1][j 1] (n (j 1))。

然后回到这个问题，主教攻击斜线，那么只要把棋盘旋转45度就和车的方法相同了。
然后黑格和白格的方案数相乘累加起来就是总方案数
代码：

#include 
   
     #include 
    
      const int N = 35; int n, k; long long f1[N][N * N], f2[N][N * N]; int main() { while (~scanf("%d%d", &n, &k) && n || k) { f1[0][0] = f2[1][0] = 1; for (int i = 1; i <= n; i++) { int len = (i + 1) / 2 * 2 - 1; f1[i][0] = f1[i - 1][0]; for (int j = 1; j <= len; j++) { f1[i][j] = f1[i - 1][j] + (len - j + 1) * f1[i - 1][j - 1]; } } for (int i = 2; i <= n; i++) { int len = i / 2 * 2; f2[i][0] = f2[i - 1][0]; for (int j = 1; j <= len; j++) { f2[i][j] = f2[i - 1][j] + (len - j + 1) * f2[i - 1][j - 1]; } } long long ans = 0; for (int i = 0; i <= k; i++) ans += f1[n][i] * f2[n][k - i]; printf("%lld\n", ans); } return 0; }