bzoj 1079 DP

DP 라 는 것 을 쉽게 알 수 있 습 니 다.그러나 우리 가 각 색상 이 몇 가지 남 았 는 지 기록 하면 소모 되 는 전이 시간 복잡 도 5^15 입 니 다.그러나 우 리 는 각 색상 을 고려 하여 수량 이 같 으 면 같은 효 과 를 가 집 니 다.그래서 우 리 는 w[a][b][c][d][e][last]로 1,2,3,4,5 번 의 사용 횟수 를 기록 한 색상 의 수량 은 a,b,c,d,e 입 니 다.지난번 에 우리 가 사용 한 횟수 가 last 로 남 은 색 이 었 다 면 이번 에는 남 은 last-1 번 의 색 중에서 우 리 는 한 번 만 덜 가 져 갈 수 있 었 다.같은 것 을 가 져 올 수 없 기 때문에 이렇게 옮 기 면 쉽게 표현 할 수 있 었 다.
저 는 저 장 된 상태의 배열 을 모두 20 까지 열 었 는데 0 mstle 에 있 습 니 다.16 으로 바 꾸 면 됩 니 다.지 도 를 구 합 니 다.

/**************************************************************

    Problem: 1079

    User: BLADEVIL

    Language: C++

    Result: Accepted

    Time:80 ms

    Memory:131876 kb

****************************************************************/

 

//By BLADEVIL

#include <cstdio>

#define LL long long

#define d39 1000000007

 

using namespace std;

 

int n,x;

int sum[20];

LL w[16][16][16][16][16][16];

 

LL calc(int a,int b,int c,int d,int e,int last) {

    if (a+b+c+d+e==0) return w[a][b][c][d][e][last]=1;  

    if (w[a][b][c][d][e][last]) return w[a][b][c][d][e][last];

    LL sum=0ll;

    if (a) (sum+=(a-(last==2))*calc(a-1,b,c,d,e,1))%=d39;

    if (b) (sum+=(b-(last==3))*calc(a+1,b-1,c,d,e,2))%=d39;

    if (c) (sum+=(c-(last==4))*calc(a,b+1,c-1,d,e,3))%=d39;

    if (d) (sum+=(d-(last==5))*calc(a,b,c+1,d-1,e,4))%=d39;

    if (e) (sum+=e*calc(a,b,c,d+1,e-1,5))%=d39;

    return w[a][b][c][d][e][last]=sum;

}

 

int main(){

    scanf("%d",&n);

    while (n--) scanf("%d",&x),sum[x]++;

    LL ans=calc(sum[1],sum[2],sum[3],sum[4],sum[5],0);

    printf("%lld
",ans);

    return 0;

}