BZOJ 1801 [Ahoi2009]中国象棋（线性动规）（洛谷P2051）

题意：就是在n*m的格子中放“炮”（中国象棋中的棋子）问有多少种放法，使得没有任意的两个炮相互攻击

思路：我们很容易的得到一列或者一行中最多放下两个炮（我也只能得到这些了，满脑子状压，但数据范围有100），这篇博客些的很好（传送门），我们定义dp[i][j][k]代表前i行我们有j列式有2个棋子，有k列是一个棋子，那么我们空的列的个数为m-i-j，我们在每行填的时候最多填2个，这样保证了我们每行不会多于2个。然后就是分情况讨论了

代码：

#include 
using namespace std;
typedef long long LL;
inline LL read()
{LL x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){ if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}const LL MOD=9999973;
LL dp[107][107][107];int main()
{int n=read(),m=read();dp[0][0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){for(int k=0;k<=m-j;k++){LL res=0;res+=dp[i-1][j][k];if(j)res+=dp[i-1][j-1][k+1]*(k+1);if(k)res+=dp[i-1][j][k-1]*(m-j-k+1);if(j&&k)res+=dp[i-1][j-1][k]*k*(m-j-k+1);if(j>1)res+=dp[i-1][j-2][k+2]*(k+2)*(k+1)/2;if(k>1)res+=dp[i-1][j][k-2]*(m-j-k+2)*(m-j-k+1)/2;dp[i][j][k]=res%MOD;}}}LL ans=0;for(int i=0;i<=m;i++){for(int j=0;j<=m-i;j++){ans=(ans+dp[n][i][j])%MOD;}}printf("%lld
",ans%MOD);return 0;
}