首页 > 其他 > 详细

深圳福利彩票官网:dtoj#2504. ZCC loves cube(cube)

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

深圳风采开奖直播 www.nskjr.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号

  • 价值-热门标签-华商生活 2019-05-19
  • 以古鉴今,习近平多次提及屈原 2019-05-18
  • 候选企业:内蒙古蒙草生态环境(集团)股份有限公司 2019-05-18
  • 埃里克森:中国将成为足球大国 15年内能进四强 2019-05-17
  • 审计署:19万套房子空置 数百亿元资金闲置 2019-05-17
  • 广东清远黑臭水体整治弄虚作假 6名责任人被立案调查 2019-05-16
  • 推动实现更高质量和更充分就业 2019-05-15
  • 暴雨突袭石泉 干部背群众转移到安全地带 2019-05-15
  • 人体-热门标签-华商生活 2019-05-14
  • 改革开放40载,互联网的发展风云激荡 2019-05-14
  • 杭州高新区(滨江):“智慧社区”助推社区治理服务创新 2019-05-13
  • 法治中国,走向更美好的明天(砥砺奋进的五年·全面依法治国) 2019-05-13
  • 斯柯达速派2017年上半年累计销量同比上涨36% 2019-05-12
  • 浙江台州副市长出庭应诉民告官案 称要作表率 2019-05-12
  • 罗品禧的专栏作者中国国家地理网 2019-05-11
  • 956| 952| 328| 436| 136| 320| 521| 621| 281| 169|