AC日记——[SCOI2008] 着色方案 bzoj 1079

1079

思路：

　　dp；

　　我们如果dp方程为15维，每维记录颜色还有多少种；

　　不仅tle，mle，它还re；

　　所以，我们压缩一下dp方程；

　　方程有6维，第i维记录有多少种颜色还剩下i次；

　　最后还要记录上次使用是第几维；

来，上代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define ll long long

#define mod 1000000007

ll n,m[],sum,ai[],dp[][][][][][];

bool if_[][][][][][];

ll dfs(ll a,ll b,ll c,ll d,ll e,ll f)

{

    if(a<||b<||c<||d<||e<) return ;

    if(a+b+c+d+e>sum) return ;

    if(a>m[]||b>m[]||c>m[]||d>m[]||e>m[]) return ;

    if(if_[a][b][c][d][e][f]) return dp[a][b][c][d][e][f];

    if_[a][b][c][d][e][f]=true;

    ll now=;

    if(f==)

    {

        now+=dfs(a,b,c,d,e+,)*(e+);

        now+=dfs(a,b,c,d,e+,)*(e+);

        now+=dfs(a,b,c,d,e+,)*e;

        now+=dfs(a,b,c,d,e+,)*(e+);

        now+=dfs(a,b,c,d,e+,)*(e+);

        now+=dfs(a,b,c,d,e+,)*(e+);

    }

    else if(f==)

    {

        now+=dfs(a,b,c,d+,e-,)*(d+);

        now+=dfs(a,b,c,d+,e-,)*(d+);

        now+=dfs(a,b,c,d+,e-,)*(d+);

        now+=dfs(a,b,c,d+,e-,)*d;

        now+=dfs(a,b,c,d+,e-,)*(d+);

        now+=dfs(a,b,c,d+,e-,)*(d+);

    }

    else if(f==)

    {

        now+=dfs(a,b,c+,d-,e,)*(c+);

        now+=dfs(a,b,c+,d-,e,)*(c+);

        now+=dfs(a,b,c+,d-,e,)*(c+);

        now+=dfs(a,b,c+,d-,e,)*(c+);

        now+=dfs(a,b,c+,d-,e,)*c;

        now+=dfs(a,b,c+,d-,e,)*(c+);

    }

    else if(f==)

    {

        now+=dfs(a,b+,c-,d,e,)*(b+);

        now+=dfs(a,b+,c-,d,e,)*(b+);

        now+=dfs(a,b+,c-,d,e,)*(b+);

        now+=dfs(a,b+,c-,d,e,)*(b+);

        now+=dfs(a,b+,c-,d,e,)*(b+);

        now+=dfs(a,b+,c-,d,e,)*b;

    }

    else if(f==)

    {

        now+=dfs(a+,b-,c,d,e,)*(a+);

        now+=dfs(a+,b-,c,d,e,)*(a+);

        now+=dfs(a+,b-,c,d,e,)*(a+);

        now+=dfs(a+,b-,c,d,e,)*(a+);

        now+=dfs(a+,b-,c,d,e,)*(a+);

        now+=dfs(a+,b-,c,d,e,)*(a+);

    }

    now%=mod;

    dp[a][b][c][d][e][f]=now;

//    printf("%d %d %d %d %d %d %lld\n",a,b,c,d,e,f,now);

    return now;

}

int main()

{

//    freopen("color.in","r",stdin);

//    freopen("color.out","w",stdout);

    cin>>n;ll pos;

    for(ll i=;i<=n;i++)

    {

        cin>>pos;

        ai[pos]++;

    }

    for(ll i=;i<=;i++)

    {

        for(ll j=i;j<=;j++) m[i]+=ai[j];

        sum+=ai[i];

    }

    dp[ai[]][ai[]][ai[]][ai[]][ai[]][]=;

    if_[ai[]][ai[]][ai[]][ai[]][ai[]][]=true;

    cout<<dfs(,,,,,);

    return ;

}

巴特西

AC日记——[SCOI2008] 着色方案 bzoj 1079

最新文章

热门文章