【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=1;i<=1000;i++)
    for(int j=i;j<=2*i;j++)
        if(i==1)dp[i][j]=2;
        else dp[i][j] = dp[i][j-1] * (2*i-j+1) %M + dp[i-1][j-1]*4 %M;

    while(scanf("%I64d",&n)&&n)
        printf("%I64d\n",dp[n][2*n]);
    return 0;
}