HDU 6114 Chess

题面

車是中国象棋中的一种棋子，它能攻击同一行或同一列中没有其他棋子阻隔的棋子。一天，小度在棋盘上摆起了许多車……他想知道，在一共N×M个点的矩形棋盘中摆最多个数的車使其互不攻击的方案数。他经过思考，得出了答案。但他仍不满足，想增加一个条件：对于任何一个車A，如果有其他一个車B在它的上方（車B行号小于車A），那么車A必须在車B的右边（車A列号大于車B）。

现在要问问你，满足要求的方案数是多少。

Input

第一行一个正整数T，表示数据组数。

对于每组数据：一行，两个正整数N和M（N<=1000，M<=1000）。

Output

对于每组数据输出一行，代表方案数模1000000007（1e9+7）。

Sample Input

1
1 1

Sample Output

1

Time limit	Memory limit	OS
1000 ms	32768 kB	Windows

题目大意

就是要给你一个$m \times n$m×n（假设$m \ge n$m≥n）的棋盘大小，要求把$n$n个棋子放到这个棋盘当中，其中对于每对棋子，都要求满足一个在左上角，一个在右下角（也即所有棋子都不同行同列，且所有棋子的分布大致是左上到右下）。问有多少种摆法（棋子都是一样的）。

题目分析

由对称可知，$m \times n$m×n和$n \times m$n×m的方案数都是一样的。我们不妨假设$m \ge n$m≥n，也就是给的都是一个$n$n行$m$m列的横着的长方形。 如图所示：

由于要放$n$n个棋子，那么我们可能的起点就是左上角黑色区域，终点，只能是右下角红色的区域了。我们先不妨先在左上角第一个格子放一个棋子。

那么蓝色区域，就是我们下一步可以走的区域了。这时我们再选择蓝色区域左上角第一个格子放一个棋子。并以此类推。


这时我们已经放完了棋子，得到了一种方案。我们再退回去选择另外的一种方案。

这时我们再退回去两层，选择另外的一种方案。这时我们不难发现，其实这就是一个DFS的过程。限定步数在$n$n个以内，寻找走到终点的方案数。而且，对于每一幅$m \times n$m×n的地图，它的下一层分支必然有$m - n + 1$m−n+1个。
同时，这个过程情况是有重复的，如下图所示：
它们的后续情况是完全一样的，所以我们不妨声明一个数组将它记下来，实现记忆化搜索。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll dp[1005][1005];
ll dfs(int n, int m){
  if(n == 0 || m == 0)
    return dp[n][m] = 1;
  if(dp[n][m] != -1)
    return dp[n][m];
  ll ans = 0;
  for(int i = 1; i <= m - n + 1; i++)
    ans +=  dfs(n - 1, m - i) % 1000000007;
  return dp[n][m] = ans;
}
int main(int argc, char const *argv[]) {
  int T;
  ll n, m;
  scanf("%d", &T);

  while(T--){
    memset(dp, -1, sizeof(dp));
    scanf("%lld%lld", &n, &m);
    if(n == 0 || m == 0)
      printf("%d\n", 0);
    else
      printf("%lld\n", n == m?1:dfs(min(n, m), max(n, m)) % 1000000007);
  }
  return 0;
}

后记

当然，这道题还可以用组合数来写，但是组合数取模那部分还不怎么会，就不写了。