SGU 221

题目描述-戳我跳转

一个$n \times n$的棋盘中有$k$个象互不相吃的情况数

这道题明显求个数,可以考虑纯数学解法(输入无数组),但正解是计数dp

解法-纯数学

当$k=2 \times n - 2$时,因为象之间不互相攻击,那么在同一个对角线上不可能存在两个棋子 但考虑到$( 1 , 1 )$与$( n , n )$不能在同一对角线上,棋子最多为$2 \times n - 2$

但这道题求的是个数,上面的这个推导是有公式的,我就不说了

解法-计数dp

首先对角线是不好做的,可以考虑旋转棋盘$45°$,把'象'变成'车'

另外$dp_{i,j}$表示前$i$行放$j$个象的方案数，首先发现一行只能放一个'车'

转移方程需讨论:

1. $dp_{i,j}=dp_{i-1,j}$ 直接从上一行转过来
2. $dp_{i,j}$是上一行少一格转来的

发现问题了吧

如果对于每一行来说,他前面所有的行的个数都小于等于他 则这一行要新添棋子有$($格子数$- j + 1 )$,所以我们先排一个序

此时第二类为$dp_{i,j}=dp_{i-1,j-1}*(a_i-j+1)$ 综上所述,$dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}*(a_i-j+1)$