首页 > 其他 > 详细

何明七乐彩14060:dtoj#2504. ZCC loves cube(cube)

时间:2019-03-13 00:45:44      阅读:77      评论:0      收藏:0      [点我收藏+]

福利彩票七乐彩开奖结果 www.0g0pi.cn 标签:积木   printf   技术   想要   目前   isp   define   相同   ans   

题目描述:

调戏完了狗,ZCC开始玩起了积木。ZCC的面前有一块 $ n \times n $ 的棋盘,他要用这些 $ 1 \times 1 $ 的积木在棋盘上搭出一个宏伟的建筑?;居腥盅丈?,ZCC认为一个建筑要被称为宏伟的应该满足能从正面看到的每一个积木都是同一种颜色。现在,ZCC想要知道他能用他拥有的积木搭出多少种宏伟的建筑。当然,为了让建筑足够大,ZCC需要用完他所有的积木。两个建筑被称为不同的当且仅当两个建筑形状不同或者存在一块相同位置不同颜色的积木。

算法标签:DP

思路:

首先枚举在视野可见的那一种颜色是什么,那么剩下两种颜色实际上没有差别,所以可以看作只有两种颜色。

考虑DP

首先我们先单独考虑一列的情况:

$g[i][j][k]$ 表示前 $i$ 行,已经用了 $j$ 个方块,目前最高的色块高度为 $k$ 的方案数。
$$
g[i][j][max(k,z)]+=g[i-1][j-z][k]
$$
(则有 $j$ 个方块必须固定为某一种颜色,其他颜色可以随机放)

$f[i][j][k]$ 表示前 $i$ 列,已经用了 $j$ 个方块,有 $k$ 各方块被强制为某一种颜色的方案数。
$$
f[i][j+x][k+y]+=f[i-1][j][k]*g[n][x][y]
$$
最后枚举哪一种颜色有多少露在表面,乘上相应的组合数。
$$
\sum_{i=0}^{r}ans+=f[n][r+g+b][i]\times C_{r+g+b-i}^{r-i}\times C_{g+b}^{g}
$$

以下代码:

技术分享图片
#include<bits/stdc++.h>
#define il inline
#define _(d) while(d(isdigit(ch=getchar())))
using namespace std;
const int N=100,p=1e9+7;
int r,G,b,n,c[N][N],g[N][N][N],f[N][N][N];
il int read(){
    int x,f=1;char ch;
    _(!)ch==-?f=-1:f;x=ch^48;
    _()x=(x<<1)+(x<<3)+(ch^48);
    return f*x;
}
il int mu(int x,int y){
    if(x+y>=p)return x+y-p;
    return x+y;
}
int main()
{
    n=read();r=read();G=read();b=read();
    int m=r+G+b,mx=max(max(r,G),b);
    for(int i=0;i<=m;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++)c[i][j]=mu(c[i-1][j-1],c[i-1][j]);
    }
    g[0][0][0]=f[0][0][0]=1;
    for(int i=1;i<=n;i++)for(int j=0;j<=m;j++)
        for(int k=0;k<=mx&&k<=j;k++)
            for(int z=0;z<=mx&&z<=j;z++){
                int kk=max(k,z);
                g[i][j][kk]=mu(g[i][j][kk],g[i-1][j-z][k]);
            }
    for(int i=1;i<=n;i++)for(int j=0;j<=m;j++)
        for(int k=0;k<=mx&&k<=j;k++){
            if(!f[i-1][j][k])continue;
            for(int x=0;x+j<=m;x++)
                for(int y=0;y+k<=mx&&y<=x;y++)
                    f[i][j+x][k+y]=mu(f[i][j+x][k+y],1ll*f[i-1][j][k]*g[n][x][y]%p);
        }
    int ans=0;
    for(int i=0;i<=r;i++)ans=mu(ans,1ll*f[n][m][i]*c[m-i][r-i]%p*c[m-r][G]%p);
    for(int i=0;i<=G;i++)ans=mu(ans,1ll*f[n][m][i]*c[m-i][G-i]%p*c[m-G][r]%p);
    for(int i=0;i<=b;i++)ans=mu(ans,1ll*f[n][m][i]*c[m-i][b-i]%p*c[m-b][r]%p);
    printf("%d\n",ans);
    return 0;
}
View Code

 

dtoj#2504. ZCC loves cube(cube)

标签:积木   printf   技术   想要   目前   isp   define   相同   ans   

原文:https://www.cnblogs.com/Jessie-/p/10520529.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
? 2014 福利彩票七乐彩开奖结果 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号

1000| 664| 552| 284| 221| 481| 398| 797| 143| 351|