JZOJ 4.15 1667——【AHOI2009】中国象棋【dp】

本文主要是介绍JZOJ 4.15 1667——【AHOI2009】中国象棋【dp】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

　　在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。请问有多少种放置方法？中国象棋中炮的行走方式大家应该很清楚吧.

Input

　　一行包含两个整数N，M，中间用空格分开.

Output

　　输出所有的方案数，由于值比较大，输出其mod 9999973

Sample Input

1 3

Sample Output

7
Hint

　　除了在3个格子中都放满炮的的情况外，其它的都可以.
　　100%的数据中N,M不超过100
　　50%的数据中，N,M至少有一个数不超过8
　　30%的数据中，N,M均不超过6
　　

题目中可见，每一行每一列最多只能放两个炮
可以设f[i][j][k]为前i行有j列放一个炮，k列放两个炮，然后分类讨论：
①不放
②在已经放过一个的放一个
③在没有放过的地方放一个
④在没有放过的地方放两个
⑤在放过一个和没有放过的地方放一个
（Tips：记住要取模）

代码如下:

#include<cstdio>  
#include<cstring>  
using namespace std;  
long long f[151][151][151];  
int main()  
{  int n,m;  scanf("%d%d",&n,&m);  memset(f,0,sizeof(f));  f[0][0][0]=1;  for (int i=0;i<n;i++)  {  for (int j=0;j<=m;j++)  {  for (int k=0;k<=j;k++)  {  if (f[i][j][k]>=9999973) f[i][j][k]%=9999973;  f[i+1][j][k]+=f[i][j][k];  if (j<m) f[i+1][j+1][k]+=f[i][j][k]*(m-j);  if (j<m-1) f[i+1][j+2][k]+=f[i][j][k]*(m-j)*(m-j-1)/2;  if (j>0&&k<j) f[i+1][j][k+1]+=f[i][j][k]*(j-k);  if (j>0&&k<j-1) f[i+1][j][k+2]+=f[i][j][k]*(j-k)*(j-k-1)/ 2;  if (j<m&&j>0&&k<j) f[i+1][j+1][k+1]+=f[i][j][k]*(m-j)*(j-k);  }  }  }  long long ans=0;  for (int i=0;i<=m;i++)  {  for (int j=0;j<=i;j++)  {  ans+=f[n][i][j];  if (ans>=9999973) ans%=9999973;  }  }  printf("%d",(int)ans);  return 0;  
}