题目

Description

话说Jby发明了一个取石子游戏之后，一下就被聪明的你破解了….
这次他又搞了一个新的游戏来折磨游戏者;
Jby会给定的一个N*N的棋盘，而且要求你在棋盘中放M个士兵，使得士兵不能互相攻击，你的任务是求出有多少种不同的方案。对于每个士兵，他的攻击范围是他的对角线。如图所示：

Input

仅有一行，两个数N和M。分别表示棋盘的大小和要放士兵的个数。

Output

仅有一行，表示方案数。

Sample Input

3 4

Sample Output

8

Data Constraint

对于60%的数据,N<=8,1<=m<=2N-2
对于100%的数据，N<=15,1<=m<=2N-2，且答案在Int64范围以内！！

分析

主要思想:把图翻转45度，那么变成2N-1行
可以发现，奇数行和偶数行是互不影响的，所以分开来做DP
分开奇偶行之后，按照长度从小到大排序
F【I,j】代表前I行放J个士兵的方案数
A【i】为第I行的空格数
F【i，j】:=F【i-1,j】（第I行不放）+F【i-1，j-1】（A【i】-j+1）（第I行可以放A【i】-j+1个位置，枚举第J个士兵放第I行的哪个位置）
偶数行的情况G【i，j】一样
（注意边界问题）
最后枚举奇数行放X个，偶数行放Y（M-x）个
就可以算出总方案数了

CODE

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;int n,m;
long long sum;
long long f[2][100];int main(){freopen("chess.in","r",stdin);freopen("chess.out","w",stdout);scanf("%d%d",&n,&m);f[0][0]=1;f[1][0]=1;for (int i=1;i<=n;i++){int x=i%2;for (int j=i;j>=1;j--)f[x][j]+=f[x][j-1]*(i-j+1);if (i<n){for (int j=i;j>=1;j--)f[x][j]+=f[x][j-1]*(i-j+1);} }for (int i=0;i<=m;i++)sum+=f[1][i]*f[0][m-i];printf("%lld\n",sum);return 0;
}