学步园

很久以前，有一个强大的帝国，它的国土成正方形状，如图2—2所示。 

这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功，国王准备给他们每人一块封地(正方形中的一格)。但是，这些诸侯又非常好战，当两个诸侯位于同一行或同一列时，他们就会开战。如下图2—3为n＝3时的国土，阴影部分表示诸侯所处的位置。前两幅图中的诸侯可以互相攻击，第三幅则不可以。 

国王自然不愿意看到他的诸侯们互相开战，致使国家动荡不安。? 因此，他希望通过合理的安排诸侯所处的位置，使他们两两之间都不能攻击。 
现在，给出正方形的边长n，以及需要封地的诸侯数量k，要求你求出所有可能的安置方案数。(n≤l00，k≤2n2-2n+1) 
由于方案数可能很多，你只需要输出方案数除以504的余数即可。 

思路：

可以将图形转化为：

分析一下问题发现，里面有重叠子问题。如果一个列作为最后一列，且这一列以及前面所有列共放置p个诸侯，设有q种情况，那么这一列后面的所有列共放置p+1个棋子的方案数都要用到q，从而引用乘法原理。而且在穷举过程中，这一个工作做了许多遍，所以干脆用递推。递推前，先把图形转化为类似以上图的形式(即列排序)。

   dp[ i ] [ j ]  =  dp [ i ] [ j ] + dp[ i - k ] [ j -1] * ( i -  j + i % 2 )

其中 dp[ i ] [ j ]指的是： 以第i列为最后一列，放置j个棋子的总方案数。

 i - j + i%2  中 i-j是以i为最后一列放置了j个棋子后没有放置棋子的列数，若x为奇数，则一定比上x-1列多两种放置方式，若x为偶数，则要避免与上一层的行数冲突，所以只多一种情况。若在x列和x-1列都放置则只有2种情况。所以若i为奇数，其中(i-1)列有i-j种方法，剩下一列是没有相同的所以该列有2种方法，即i为奇数时有:（i-1）+2 = i+1种 ，i为偶数时有： i 种。

#include<iostream>
#include<string.h>
using namespace std;
int main()
{
    int n,m;
    int dp[300][300];
    while(scanf("%d%d",&n,&m)!=EOF)
    {
         if(m==0) { printf("1\n"); continue; }
         if(m>=2*n-1) { printf("0\n");  continue;}
         memset(dp,0,sizeof(dp));
         for(int i=1;i<=2*n-1;i++)
         if(i%2) dp[i][1]=i ; //在i列（包括i列之前）放置1个，有i种情况（奇数） 
         else dp[i][1]=i-1;  //为偶数时，只有i-1个空位，所以之多i-1种情况。 
         for(int i=1;i<=2*n-1;i++)
         {
              for(int j=2;j<=i;j++)
              {
                  for(int k=1;k<=i-j+1;k++)
                  {
                      dp[i][j]+=dp[i-k][j-1]*(i-j+i%2);
                      dp[i][j]%=504;
                  }
              }
         }
         for(int i=m;i<2*n-1;i++)
         {
             dp[2*n-1][m]+=dp[i][m];
             dp[2*n-1][m]%=504;
         }
         
         printf("%d\n",dp[2*n-1][m]);
    }
    return 0;
}