【Gym 100015B】Ball Painting(DP染色)
There are 2N white balls on a table in two rows, making a nice 2-by-N rectangle. Jon has a big paint bucket
full of black paint. (Don’t ask why.) He wants to paint all the balls black, but he would like to have some
math fun while doing it. (Again, don’t ask why.) First, he computed the number of different ways to paint
all the balls black. In no time, he figured out that the answer is (2N)! and thought it was too easy. So, he
introduced some rules to make the problem more interesting.
• The first ball that Jon paints can be any one of the 2N balls.
• After that, each subsequent ball he paints must be adjacent to some black ball (that was already
painted). Two balls are assumed to be adjacent if they are next to each other horizontally, vertically,
or diagonally.
Jon was quite satisfied with the rules, so he started counting the number of ways to paint all the balls
according to them. Can you write a program to find the answer faster than Jon?
B.1 Input
The input consists of multiple test cases. Each test case consists of a single line containing an integer N,
where 1 ≤ N ≤ 1,000. The input terminates with a line with N = 0. For example:
1
2
3
0
B.2 Output
For each test case, print out a single line that contains the number of possible ways that Jon can paint all
the 2N balls according to his rules. The number can become very big, so print out the number modulo
1,000,000,007. For example, the correct output for the sample input above would be:
2
24
480
题意
给你两行n列的2*n个球,一开始你随意选一个涂黑色,接着必须在黑色球相邻的球里选择一个再涂黑色,可以斜着相邻,求涂完2n个球有多少种涂法。
分析
递推没办法,只能动态规划,f[i][j]表示,染色长度为i的两行矩阵,染了j个球的方案数,染色长度就是指这连续的i列每列至少有一个球染色了,按照规则可知染色的球一定在一个染色矩阵里,就是不会有隔了一列的染了色的球。
状态转移方程:
f[i][j]+=f[i][j-1]*(2*i-(j-1)) 表示在i列里选择没有染色的球2*i-(j-1)进行染色,他们肯定可以染色。
f[i][j]+=f[i-1][j-1]*4 表示它可以从少一列的染色矩阵的外部左边或者右边共四个球里选一个染色后,获得的i列染色矩阵。
代码
#include<stdio.h>
#define N 1005
#define M 1000000007
long long dp[N][N],n;
int main(){
for(int i=;i<=;i++)
for(int j=i;j<=*i;j++)
if(i==)dp[i][j]=;
else dp[i][j] = dp[i][j-] * (*i-j+) %M + dp[i-][j-]* %M; while(scanf("%I64d",&n)&&n)
printf("%I64d\n",dp[n][*n]);
return ;
}
最新文章
- 用uniq来处理文件重复数据--交集,差集,计数等(转)
- 外接程序“VMDebugger”未能加载或者导致了异常。是否希望移除该外接程序?
- freemarker 数据做加减计算
- Java字节流:FilterInputStream FilterOutputStream
- 解析php file_exists无效的解决办法
- js模块,类,继承,命名空间,私有属性等相关概念梳理
- Linux中如何新建用户
- 剑指offer-面试题8.旋转数组的最小数字
- LeetCode OJ 101. Symmetric Tree
- 移动设备真机调试本地程序的Node.js【无需连wifi】
- UiAutomator2.0升级填坑记
- prim及其练习
- NO.10: 在operator=中处理 ";自我赋值";
- 快速排序中BUG int 与 int *
- sql 中延时操作
- ubuntu搭建discuz论坛
- winform弹出文件和目录选择框
- 文件上传 python
- Python 的AES加密与解密-需要安装的模块
- Yii1.1应用升级到Yii2.0的一些注意点