首页 > 其他 > 详细

Codeforces 128C Games with Rectangle

时间:2014-01-16 00:02:16      阅读:494      评论:0      收藏:0      [点我收藏+]

题意:给定一个n*m的有格子的矩形,现在又两个人在矩形内轮流画矩形,每次都必须沿着格子的轮廓来画,新画的矩形必须嵌套在上一个矩形里面,并且不能和上一个矩形有任何的重复的点。现在这两个人一共会画k次,问一共有多少种不同的画法。

这是一个相当好的排列组合题。当然也可以用DP来解。

解决本题最最最关键的是要认识到,n和m两个维度是相互独立的,它们互不干扰。

这样,可以先来解决线段嵌套的问题,假设我们现在又一根长为M的线段,每1米有一个标记点,现在给你K次机会,不断的从当前的线段的中部去截取一部分,每次截取的时候必须以标记点为端点,问你一共有多少种方法。这显然是C(M-1,2*K)种。为什么呢?因为这相当于从线段的M-1个标记点上(两端不算)上任选2*K个点,比如说要截取2次,那肯定选了4个点,从左至右分别是a1,a2,a3,a4,那么自然就形成了第一次截取的是a1a4,第二次截取的是a2a3,所以答案就是C(M-1,2*K)种。

现在问题变成了二维的了,那么答案还是很简单,就是C(m-1,2*k)*C(n-1,2*k)

有的时候,如果能从题目中提取出独立的子问题,那么题目就非常容易解决了。

bubuko.com,布布扣
 1 #include <stdio.h>
 2 typedef long long LL;
 3 const int MOD = 1000000007;
 4 LL C[1<<10][1<<11];
 5 
 6 void init(){
 7     C[0][0] = 1;
 8     for(int i = 0;i < (1<<10);i++){
 9         C[i][0] = C[i][i] = 1;
10         for(int j = 1;j < i;j++)
11             C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
12     }
13 }
14 
15 int main(){
16     init();
17     int n,m,k;
18     scanf("%d%d%d",&n,&m,&k);
19     printf("%lld\n",(C[n-1][2*k] * C[m-1][2*k]) % MOD);
20     return 0;
21 }
View Code

Codeforces 128C Games with Rectangle

原文:http://www.cnblogs.com/zhexipinnong/p/3516478.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!