首页 > 代码库 > UVA 10237 - Bishops(递推)
UVA 10237 - Bishops(递推)
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 <stdio.h>
#include <string.h>
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;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。