Chess(百度之星初赛B）

本文主要是介绍Chess(百度之星初赛B），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Chess Accepts: 1805 Submissions: 5738
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
車是中国象棋中的一种棋子，它能攻击同一行或同一列中没有其他棋子阻隔的棋子。一天，小度在棋盘上摆起了许多車……他想知道，在一共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

正解

百度之星竟还有这么简单的题目。
车一定最多能摆MIN（n,m）。那么，这题就很简单了。
可以考虑设f[i,j,k]为棋盘大小为i行j列，已经摆放了k个棋子的方案数。
f[i,j,k]:=f[i-1,j,k]+f[i,j-1,k]+f[i-1,j-1,k-1].
时间复杂度：O（n*m*n)，最大为：O（1000000000）
空间复杂度：O（n*m*n)，最大为：O（1000000000）
这明显是不行的。那么，考虑优化。
发现如果摆放的棋子是最多的，那么行或者列一定是被摆满的，那么就没有必要将行或者列来循环一次。就是说，假设n小于m，那么这n行一定都有棋子。我们便没有必要去枚举一边行，枚举列就行了。如果m小于n则反之。
可以设f[i,j]为在第i个行或列，已经摆放了j个棋子的方案数。
f[i,j]:=f[i-1,j]+f[i-1,j-1]
边做边mod就行了。

代码

varf:array[0..1000,-1..1000] of longint;i,j,n,m,t,p,k:longint;
beginread(t);for i:=1 to t dobeginread(n,m);if n<m thenbeginfillchar(f,sizeof(f),0);f[1,1]:=1;f[1,0]:=1;for j:=2 to m dobeginfor k:=0 to n dobegin      f[j,k]:=(f[j-1,k-1]+f[j-1,k]) mod 1000000007;end;end;writeln(f[m,n]);endelsebeginfillchar(f,sizeof(f),0);f[1,1]:=1;f[1,0]:=1;for j:=2 to n dobeginfor k:=0 to m dobeginif (j=1) and (k=0) thencontinue;f[j,k]:=(f[j-1,k-1]+f[j-1,k]) mod 1000000007;end;end;writeln(f[n,m]);end;end;
end.