bzoj4313 三维积木-白红宇

bzoj4313 三维积木

阅读量：6208 次

发布时间：2019-06-21

本文共 1787 字，大约阅读时间需要 5 分钟。

分析

我们假设主视图的颜色为1

如果只有两种颜色，且能求出w[x][y]表示一列中放置x个1和y个2的方案数

则我们可用dp[i][j][k]表示考虑到第i列放j个1和k个2的方案数，这样的复杂度为$O(n^5)$

我们可以把颜色2和颜色3统一看成颜色2，最后方案数乘上$C_{b+c}^b$即可

于是我们考虑如何求出w[x][y]

我们可以再将这两种颜色看为一种，设ddp[i][j]表示在这一列放i个积木，最高高度恰好为j的方案数

不难得出

w[x][y] = $\sum_{i=1}^x$ddp[x+y][i] * $C_{x+y-i}^{x-i}$

至于如何求ddp[i][j]我们可以再数组最后再加以为[0/1]表示是否出现过高度为j的情况

用前缀和优化一下即可使求这个的过程变为$O(n^2)$

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;const int mod = 1e9+7;int w[110][110],ddp[110][110][2],dp[110][110][110],C[110][110];int pre[110][110][2];inline void getc(){ int i,j,k; for(i=0;i<=100;i++)C[i][0]=C[i][i]=1; for(i=1;i<=100;i++) for(j=1;j
                   
                    >a>>b>>c>>n; m=max(a,max(b,c)); getc(); for(i=1;i<=m;i++) for(j=0;j<=2*m;j++) for(k=1;k<=i;k++){ memset(ddp,0,sizeof(ddp)); memset(pre,0,sizeof(pre)); for(p=0;p
                    
                     =0?pre[p-1][q-k-1][1]:0) +(q-k>=0?ddp[p-1][q-k][0]:0))%mod; if(ddp[p][q][1]<0)ddp[p][q][1]+=mod; ddp[p][q][0]=(pre[p-1][q][0]-(q-k>=0?pre[p-1][q-k][0]:0))%mod; if(ddp[p][q][0]<0)ddp[p][q][0]+=mod; pre[p][q][1]=((q>0?pre[p][q-1][1]:0)+ddp[p][q][1])%mod; pre[p][q][0]=((q>0?pre[p][q-1][0]:0)+ddp[p][q][0])%mod; } w[i][j]=(w[i][j]+ (long long)ddp[n][i+j][1]*C[i+j-k][i-k]%mod)%mod; } w[0][0]=1; dp[0][0][0]=1; for(i=1;i<=n;i++) for(j=0;j<=m;j++) for(k=0;k<=2*m;k++) for(p=0;p+j<=m;p++) for(q=0;q+k<=2*m;q++) dp[i][j+p][k+q]=(dp[i][j+p][k+q]+ (long long)dp[i-1][j][k]*w[p][q]%mod)%mod; Ans=((long long)dp[n][a][b+c]*C[b+c][b]%mod +(long long)dp[n][b][a+c]*C[a+c][a]%mod +(long long)dp[n][c][b+a]*C[b+a][b]%mod)%mod; printf("%d\n",Ans); return 0;}