首页 > 代码库 > HDU 5155 Harry And Magic Box

HDU 5155 Harry And Magic Box

问题描述
有一天,哈利得到了一个神奇的盒子。这个盒子由n*m个格子组成,有一些格子里会有闪闪发光的宝石。但是盒子的顶部和底部都被神奇的魔法封印着,所以哈利没办法从顶部和底部看到盒子的内部。然而,盒子的四边都是透明的,哈利可以从盒子的四边看到里面的情况。哈利发现,这个神奇的盒子,从左边看过去,每一行都闪烁着光芒,从前面看过去,每一列也都闪烁着光芒。哈利想知道,盒子里的宝石有多少种分布情况。答案有可能很大,所以输出答案对1000000007取模。
输入描述
多组输入数据
每组数据一行,输入两个数n m表示盒子的大小,0n,m50
输出描述
每组数据输出一行,一个整数,代表方案数
思路:一种棋盘类型的DP,按行扩展,以为每一行都必须有棋子,所以枚举每一行填充的棋子的数目,
dp[i][j]表示已扩展到第i行,其中已有j列有棋子的方案数。
则  dp[i+1][j+t] += dp[i][j] * C[m-j][t] * C[j][k-t]  (k为第i+1行填充棋子数,t为新增列数)
代码:
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod = 1000000007;
const int N = 100+10;
typedef long long ll;
ll C[N][N];
ll dp[N][N];
int n,m;
void init()
{
    memset(C,0,sizeof(C));
    for(int i=0;i<=60;i++) C[i][0]=1;
    for(int i=1;i<=50;i++)
        for(int j=1;j<=i;j++)
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
}
ll solve()
{
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=m;i++)
    {
        dp[1][i] = C[m][i];
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=1;k<=m;k++)
                for(int t=0;t<=k&&t<=m-j;t++)
                dp[i+1][j+t] = (dp[i+1][j+t] + ((dp[i][j]*C[m-j][t])%mod*C[j][k-t])%mod )%mod;
    return dp[n][m];
}
int main()
{
    init();
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        printf("%d\n",solve());
    }
    return 0;
}


HDU 5155 Harry And Magic Box