首页 > 代码库 > SGU 220.Little Bishops(DP)
SGU 220.Little Bishops(DP)
题意：
给一个n*n的棋盘，放上k个主教（斜走），求能放置的种类总数。
Solution：
一眼看上去感觉是状压DP，发现状态太多，没办法存下来。。。
下面是一个十分巧妙的处理：
将棋盘按照国际象棋的样子分成黑白两部分，再旋转45°，以黑色为例，一行有1,3,5,7。。。5,3,2,1个格子，
可以处理为1,1,3,3,5,5,7。。。
f[i][j]代表第i层，放了j个棋子的方案数，只要预处理出每一行可以放的个数tem[i]
f[i][j]=f[i-1][j]+f[i-1][j-1]*(tem[i]-j+1),tem[i]>=j;
同样对白色部分如此处理，最后将对应的黑白方案乘起来累加就好了。
注意答案会超过INT
code
#include <iostream>#include <cstdio>using namespace std;long long f[2][100][100], ans;int tem[100];int n, k, tol;void make (int x) { tol = 0; for (int t = x; t <= n; t += 2) { tem[++tol] = t; if (t != n) tem[++tol] = t; } f[x - 1][0][0] = 1; for (int i = 1; i <= tol; i++) for (int j = 0; j <= k; j++) if (tem[i] >= j) f[x - 1][i][j] = f[x - 1][i - 1][j]+f[x - 1][i - 1][j - 1] * (tem[i] - j + 1);}int main() { scanf ("%d %d", &n, &k); make (1); make (2); for (int i = 0; i <= k; i++) ans += f[1][tol][i] * f[0][2 * n - 1 - tol][k - i]; printf ("%I64d", ans);}
SGU 220.Little Bishops(DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。