[SCOI2008]着色方案

题意：
给你n种染料，每种染料可以使用Ci次，同一种染料不能连续使用，求用完所有染料的方案数为多少种？

思路：
纯动态规划，我们用dp[a][b][c][d][e][last]描述一个还可以使用一次的染料为a种，还可以使用两次的染料为b种，.....,可以使用五次的染料为f种时上一次染色为使用还可以使用last次的染料。
我们可以分析状态是怎么来的得出状态转化方程，例如，dp[a][b][c][d][e][1]时，如果上上次不为2，则上一次则使用的为a+1种染料的其中一种，如果上上次为2，则说明上一次(a+1)种有一种不能使用，所以为a种中的其中一种。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

#define inf 1000000007
#define eps 0.00000001
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int maxn=100005;

inline int read()
{
    char c=getchar();
    int f=1, x=0;
    while(c>'9'||c<'0')
    {
        if(c=='-')
        {
            f=-1;
        }
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return f*x;
}

ll dp[20][20][20][20][20][10], a[10];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int c;
        scanf("%d",&c);
        a[c]++;
    }
    dp[a[1]][a[2]][a[3]][a[4]][a[5]][1]=1;
    for(int r=n;r>=0;r--)
    {
        for(int l=n;l>=0;l--)
        {
            for(int k=n;k>=0;k--)
            {
                for(int j=n;j>=0;j--)
                {
                    for(int i=n;i>=0;i--)
                    {
                        ll p=0;
                        for(int o=1;o<=5;o++)
                        {
                            if(o==2)
                            {
                                p=p+dp[i+1][j][k][l][r][o]*(i);
                                p=p%inf;
                            }
                            else
                            {
                                p=p+dp[i+1][j][k][l][r][o]*(i+1);
                                p=p%inf;
                            }
                        }
                        dp[i][j][k][l][r][1]=max(dp[i][j][k][l][r][1],p);
                        p=0;
                        for(int o=1;o<=5;o++)
                        {
                            if(i!=0)
                            {
                            if(o==3)
                            {
                                p=p+dp[i-1][j+1][k][l][r][o]*(j);
                                p=p%inf;
                            }
                            else
                            {
                                p=p+dp[i-1][j+1][k][l][r][o]*(j+1);
                                p=p%inf;
                            }
                            }
                        }
                        dp[i][j][k][l][r][2]=max(dp[i][j][k][l][r][2],p);
                        p=0;
                        for(int o=1;o<=5;o++)
                        {
                            if(j!=0)
                            {
                            if(o==4)
                            {
                                p=p+dp[i][j-1][k+1][l][r][o]*(k);
                                p=p%inf;
                            }
                            else
                            {
                                p=p+dp[i][j-1][k+1][l][r][o]*(k+1);
                                p=p%inf;
                            }
                            }
                        }
                        dp[i][j][k][l][r][3]=max(dp[i][j][k][l][r][3],p);
                        p=0;
                        for(int o=1;o<=5;o++)
                        {
                            if(k!=0)
                            {
                                if(o==5)
                                {
                                    p=p+dp[i][j][k-1][l+1][r][o]*l;
                                    p=p%inf;
                                }
                                else
                                {
                                    p=p+dp[i][j][k-1][l+1][r][o]*(l+1);
                                    p=p%inf;
                                }
                            }
                        }
                        dp[i][j][k][l][r][4]=max(dp[i][j][k][l][r][4],p);
                        p=0;
                        for(int o=1;o<=5;o++)
                        {
                            if(l!=0)
                            {
                                    p=p+dp[i][j][k][l-1][r+1][o]*(r+1);
                                    p=p%inf;
                            }
                        }
                        dp[i][j][k][l][r][5]=max(dp[i][j][k][l][r][5],p);
                        //printf("%d\n",dp[1][1][1][0][0][0]);
                    }
                }
            }
        }
    }
    cout << dp[0][0][0][0][0][1] << endl;
    return 0;
}