HDU-6114
2024-09-01 20:28:27
車是中国象棋中的一种棋子,它能攻击同一行或同一列中没有其他棋子阻隔的棋子。一天,小度在棋盘上摆起了许多車……他想知道,在一共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
题解:
这个题建议读者看一下8皇后这个经典题,估计这个就回会了;典型的DP问题。求出动态转移方程
DP[i][j]=DP[i][j-1]+DP[i-1][j-1];
AC代码为:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int mod = 1e9 + 7;
long long dp[1005][1005];
int main()
{
for (int i = 1; i<1005; i++)
{
dp[1][i] = i;
}
for (int i = 2; i<1005; i++)
{
for (int j = i; j<1005; j++)
{
if (i == j)
{
dp[i][j] = 1;
}
else
{
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1]) % mod;
}
}
}
int T;
cin >> T;
while (T--)
{
int N, M;
cin >> N >> M;
if (N>M)
{
swap(N, M);
}
cout << dp[N][M] % mod << endl;
}
return 0;
}
最新文章
- 基础知识系列☞C#中数组Array、ArrayList和List三者的区别
- github配置
- http://blog.csdn.net/pi9nc/article/details/23169357
- Mailing API
- 实用的JavaScript技巧、窍门和最佳实践
- 关于http状态码204理解
- ASP.NET站点安全
- 私人定制javascript中对象小知识点(Only For Me)
- hibernate中对象的3种状态----瞬时态、持久态、脱管态
- 驱动中如何给ring3层应用程序提权
- cassandra 堆外内存管理
- SD详解-销售过程
- Java创建对象的4种方式
- HOJ3237----BFS/DFS
- angular 自定义指令参数详解
- HDU4747——2013 ACM/ICPC Asia Regional Hangzhou Online
- [翻译] YLGIFImage 高效读取GIF图片
- 1-24-case流程控制和while循环语句的使用
- react+antd 选项卡切换
- HDU1158:Employment Planning(线性dp)