本文主要是介绍关于百度之星初赛B的A题Chess，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
，**地址：**Problem - 6114
http://acm.hdu.edu.cn/showproblem.php?pid=6114
题目
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
Source
2017”百度之星”程序设计大赛 - 初赛（B）
思路：
这次比赛完全不在状态，不知道什么问题，一个题目也没有做出来就算了。这个题目以前做过类似的。这次九改变了一下，还是没有做出来。
其实，后来自己也想了很久，开始自己没有仔细找规律，不愿意动手。后来终于找到了一些规律。类似这种有递归跟dp 有关系，然后又是这种类似规律的。一般跟杨辉三角有关系。有或者是用简单的dp递归。。下面是我们发现的规律。对了这里还有一个注意的地方。题目说是n*m个点。所以1*1只有一个点。你是一个矩形。自己开始想错了。所以你可以把那个点看成一个矩形。（有大佬一个排列组合直接写出来了，在我的收藏里面有百度之星的四个题目）
从上面举得例子可以看出来，除了第一行和第一列，当i
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define x 1000000007;
int a[1001][1001];
int main(){int i,j;int t;cin>>t; int n,m;for(i=1;i<1001;i++){for(j=1;j<1001;j++){if(j==1)a[i][j]=i;else if(i==1)a[i][j]=j;else if(j<i){a[i][j]=(a[i-1][j-1]+a[i-1][j])%x;}else if(j==i)a[i][j]=1;else a[i][j]=(a[i][j-1]+a[i-1][j-1])%x;}}while(t--){cin>>n>>m;cout<<a[n][m]<<endl;}return 0;
}还有别人不一样的做法，时用dp的。附上别人的网址
http://blog.csdn.net/lventricmt/article/details/77146109#
还有一个跟这个差不多的题目。不过那个题目，比这个数据更大。并且，不能打表了了只能，递推了或者找到了规律公式（跟杨辉三角有关）。而且还有逆元等相关知识。
附上题目网址：（瞬间移动，本人收藏了瞬间移动的解法。很神奇）
15 16校内 - Virtual Judge
http://172.22.164.136:8080/vjudge/contest/view.action?cid=36#problem/G
这篇关于关于百度之星初赛B的A题Chess的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
