题意：

有n个木块排成一行，有k种颜色的油漆，其中第i种颜色的油漆足够涂ci个木块，所有油漆刚好足够涂满所有木块。求任意两个相邻木块颜色不同的着色方案。k≤15，ci≤5

题解：

解决本题关键是ci≤5，所以以剩余可涂方块数为1,2,3,4,5及上次涂的色这次剩余可涂方块数为状态，做dp就行了。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define ll long long 6 #define mod 1000000007 7 using namespace std; 8  9 ll f[16][16][16][16][16][6],k,c[16],rem[6];10 ll dfs(int a,int b,int c,int d,int e,int g){11     if(a+b+c+d+e==0)return 1; long long &ff=f[a][b][c][d][e][g];12     if(ff!=-1)return ff; ff=0;13     if(a)ff=(ff+(ll)(a-(g==1))*dfs(a-1,b,c,d,e,0))%mod;14     if(b)ff=(ff+(ll)(b-(g==2))*dfs(a+1,b-1,c,d,e,1))%mod;15     if(c)ff=(ff+(ll)(c-(g==3))*dfs(a,b+1,c-1,d,e,2))%mod;16     if(d)ff=(ff+(ll)(d-(g==4))*dfs(a,b,c+1,d-1,e,3))%mod;17     if(e)ff=(ff+(ll)(e-(g==5))*dfs(a,b,c,d+1,e-1,4))%mod;18     return ff;19 }20 int main(){21     scanf("%d",&k); inc(i,1,k)scanf("%d",&c[i]),rem[c[i]]++;22     memset(f,-1,sizeof(f)); printf("%lld",dfs(rem[1],rem[2],rem[3],rem[4],rem[5],0));23     return 0;24 }
       
      
     

 

20160517